Problem overview
The class Codec has two methods. encode takes a List<String> and returns one String that holds all of them. decode takes that string and returns the original list, in the same order. The lesson's tests encode with one Codec object and decode with another, so decode can rely only on the string it receives, never on fields set during encode.
The strings may contain any printable character, including #, digits and spaces, and a string may be empty. For ["lint", "code", "love", "you"] the encoded string is 4#lint4#code4#love3#you, and decoding it gives the same four strings back. The list ["3#a", "", "#"] encodes to 3#3#a0#1## and also decodes back unchanged.
Approach: write the length first
The obvious plan is to join the strings with a separator, such as #, and split on it later. That fails because any character you choose can also appear inside a string. If "#" is one of the strings, a split cuts it in the wrong place.
The fix is to stop looking for a boundary at all. Before each string, write its length, then a #, then the string itself. The decoder reads the digits up to the first #, converts them to a number, and takes exactly that many characters, whatever they are. The next piece starts right after them. The characters inside a string are never inspected, so #, digits and spaces inside it cause no trouble.
The # after the length is still needed. Without it, a string that starts with a digit would run into its own length: "1" followed by "2" could be read as the length 12. Because the length is made only of digits, the first # after the start of a piece is always the one encode wrote.
Both methods must run in O(N), where N is the total length of all the strings. That shapes two details. The encoder uses a StringBuilder, since adding to a String in a loop copies everything built so far each time. The decoder moves an index through s and never cuts s into shorter copies.
Step by step
encode
- Create a
StringBuildernamedencodedto collect the pieces. - Loop over each
String sinstrs. - Append the piece for
s: its length, the character'#', thens.appendreturns the builder, so the three calls chain on one line. - Return
encoded.toString()after the loop.
decode
- Create the result list, an empty
ArrayListnamedstrs. - Keep an index
iat 0. It marks where the next piece starts. - Loop while
i < s.length(). Each round reads one piece. - Start a second index
jatiand move it forward untils.charAt(j)is'#'. The digits of the length lie betweeniandj. - Parse the digits with
Integer.parseInt(s.substring(i, j))intolength. - Add the string itself: the
lengthcharacters that start atj + 1. The end position ofsubstringis exclusive, so it isj + 1 + length. - Move
itoj + 1 + length, where the next length begins. - Return
strsafter the loop.
The solution in Java
class Codec {
public String encode(List<String> strs) {
StringBuilder encoded = new StringBuilder();
for (String s : strs) {
encoded.append(s.length()).append('#').append(s);
}
return encoded.toString();
}
public List<String> decode(String s) {
List<String> strs = new ArrayList<>();
int i = 0;
while (i < s.length()) {
int j = i;
while (s.charAt(j) != '#') {
j++;
}
int length = Integer.parseInt(s.substring(i, j));
strs.add(s.substring(j + 1, j + 1 + length));
i = j + 1 + length;
}
return strs;
}
}
A few Java details matter here:
appendoverloads.StringBuilder.appendaccepts anint, acharand aString.append(s.length())adds the decimal digits of the number, not a character with that code.append('#')adds one character.- The
charcomparison.s.charAt(j) != '#'compares twocharvalues with!=, which is correct for primitives. Strings, by contrast, must be compared withequals. substring(start, end)includesstartand excludesend. Since Java 7 it copies only the requested characters, so each string costs time proportional to its own length.ArrayList<>uses the diamond operator, so the element type comes from the declared typeList<String>.
Complexity
Time: O(N) for both methods. encode appends each string once, and the length digits add a small amount per string. decode visits each character of s once: the inner loop scans the digits, and substring copies the piece. The index i only moves forward.
Space: O(N). The encoded string and the decoded list each hold all the characters.
Edge cases and common mistakes
- Empty list. It encodes to the empty string, and
decode("")never enters the loop, so it returns an empty list. - A list with one empty string. It encodes to
0#, which differs from the empty string. Decoding0#gives a list of size 1, and decoding""gives a list of size 0, so the two cases stay apart. - Strings that look like the format.
["12#", "a b"]encodes to3#12#3#a b. The decoder reads 3, takes12#, reads the next 3, and takesa b. It never reads inside a string. - Using a separator only. Splitting on
#breaks for any string that contains one. - Skipping the
#after the length. A string starting with a digit can no longer be told apart from its length. - Forgetting
+ 1. Starting the substring atjincludes the#in the string, and movingitoj + lengthlands one character too early. - Using
String +=inencode, or cuttingsinto shorter copies indecode. Both give correct results but copy the data repeatedly, which is too slow for large inputs. - Counting
length()as bytes.length()countscharvalues, andsubstringuses the same unit, so the two stay consistent for any text.
Testing
["lint", "code", "love", "you"]encodes to4#lint4#code4#love3#youand decodes back to the same list.["3#a", "", "#"]encodes to3#3#a0#1##and decodes back to the same list.[]encodes to the empty string and decodes to an empty list.["", ""]encodes to0#0#and decodes to two empty strings.["12#", "a b"]encodes to3#12#3#a band decodes back to the same list.
