Sweaty Imposter

Encode and Decode Strings

MediumArrays & HashingBlind 75MidOpen on LeetCodeUpdated

Design a codec for lists of strings. encode(strs) turns a list of strings into one string, and decode(s) turns that string back into the original list. The strings may contain any characters, including whatever delimiter you pick, and may be empty. decode(encode(strs)) must return exactly strs for every input, including an empty list.

Examples

strs = ["hi","there"] returns ["hi","there"]

With length prefixes, the encoded string is "2#hi5#there", and decoding reads each length before its text.

strs = ["a#b",""] returns ["a#b",""]

The encoding is "3#a#b0#". The # inside "a#b" is safe because the decoder reads exactly three characters after the prefix, and the empty string encodes as "0#".

strs = [] returns []

An empty list encodes to the empty string, which decodes back to an empty list.

Constraints

  • 0 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] may contain any character, including #.

Hints

Hint 1

If you join with a comma, what breaks when one of the strings contains a comma?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Any single delimiter can appear inside a string, so prefix each string with its length and a separator: "5#there". To decode, start at index i, find the next # (it always ends the length, because digits come first), parse the number between, take exactly that many characters after the #, and jump i past them. The content is never scanned for delimiters, so it can hold anything. O(total characters) for both directions.

Time

O(total characters)

Space

O(total characters)

Pitfall

Joining with a delimiter, or escaping only some characters. A string that contains the delimiter splits in the wrong place, and a lone empty string is indistinguishable from an empty list.

Solutions

public class Codec {
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for (String s : strs) sb.append(s.length()).append('#').append(s);
        return sb.toString();
    }

    public List<String> decode(String s) {
        List<String> out = new ArrayList<>();
        int i = 0;
        while (i < s.length()) {
            int hash = s.indexOf('#', i);
            int len = Integer.parseInt(s.substring(i, hash));
            out.add(s.substring(hash + 1, hash + 1 + len));
            i = hash + 1 + len;
        }
        return out;
    }
}
Drill This