271. Encode and Decode Strings

NeetCode: Encode and Decode Strings · LeetCode: 271. Encode and Decode Strings · Difficulty: Medium

Design a Codec class with encode and decode so that a List<String> can be turned into a single string and recovered exactly. The strings may contain any character, including the ones you might pick as separators.

Example

Input:  ["neet", "code", "love", "you"]
encode -> one string
decode -> ["neet", "code", "love", "you"]

Brute force: join with a delimiter

Join the strings with a separator such as # and split on it when decoding. String.join glues the strings together and split("#", -1) cuts at every #. The -1 keeps trailing empty strings, which split would otherwise drop. This is fine until a string contains the separator itself: ["a#b"] would decode as two strings.

import java.util.Arrays;
import java.util.List;

class Codec {
    public String encode(List<String> strs) {
        return String.join("#", strs);
    }

    public List<String> decode(String s) {
        return Arrays.asList(s.split("#", -1));
    }
}

public class Main {
    public static void main(String[] args) {
        Codec codec = new Codec();
        List<String> ok = List.of("neet", "code");
        System.out.println(codec.decode(codec.encode(ok)));

        List<String> tricky = List.of("a#b");
        System.out.println(codec.decode(codec.encode(tricky)));
    }
}

[neet, code]
[a, b]

The lists print without quotes. The second line shows the bug: one string came back as two. Escaping the separator would patch this, but length-prefixing avoids escaping altogether.

Optimal: length prefix

Write each string as <length>#<text>. When decoding, read digits up to the # to learn the length n, then take exactly the next n characters as the string without looking at their content. Even if the text contains # or digits, it is never parsed, because decoding skips by length.

Walkthrough for ["ab", "c#"]: the encoding is 2#ab2#c#. Read 2, take ab; read 2, take c#.

import java.util.ArrayList;
import java.util.List;

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

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

public class Main {
    public static void main(String[] args) {
        Codec codec = new Codec();
        List<String> tricky = List.of("a#b", "2#x", "", "neet");
        String encoded = codec.encode(tricky);
        System.out.println(encoded);
        System.out.println(codec.decode(encoded));
        System.out.println(codec.decode(encoded).equals(tricky));
    }
}

3#a#b3#2#x0#4#neet
[a#b, 2#x, , neet]
true

The lists print without quotes, so the empty string appears as nothing between two commas.

Time: O(total length) for both functions. Space: O(total length).

String.length() counts UTF-16 code units, and substring uses the same units, so the prefix always matches the slice taken from it. This holds for any text, including characters outside the basic range, because decoding cuts only at the boundaries the encoder wrote. An empty list encodes to the empty string and decodes back to an empty list.