Course4all
Join us on telegram
Home/dsa/Arrays & Hashing/Encode and Decode Strings

Encode and Decode Strings

Master this topic with zero to advance depth.

Encode and Decode Strings

Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.

Visual Representation

Input: ["hello", "world"] Encoding: length + '#' + string "hello" -> "5#hello" "world" -> "5#world" Result: "5#hello5#world" Decoding: Read length, skip '#', read N chars.
Medium

Examples

Input: ["hello", "world"]
Output: ["hello", "world"]
Approach 1

Level I: Simple Delimiter (Risk: Collision)

Intuition

Join strings with a semicolon or other delimiter. This fails if a string itself contains the delimiter.

⏱ O(N)💾 O(N)

Detailed Dry Run

["a;b", "c"] -> "a;b;c" -> Decodes to ["a", "b", "c"] (Error!)

java
public class Codec {
    public String encode(List<String> strs) {
        return String.join(";", strs);
    }
    public List<String> decode(String s) {
        return Arrays.asList(s.split(";", -1));
    }
}
Approach 2

Level II: Length + Separator (Standard)

Intuition

Prefix each string with its length followed by a special character (e.g., '#'). When decoding, read the length, skip '#' and take that many characters.

⏱ O(N)💾 O(N)

Detailed Dry Run

["leet", "code"] -> "4#leet4#code" Read 4, skip #, read 'leet'. Read 4, skip #, read 'code'.

java
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> res = 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));
            res.add(s.substring(j + 1, j + 1 + length));
            i = j + 1 + length;
        }
        return res;
    }
}
Approach 3

Level III: Optimal Solution (Base64 Encoding / Escaping)

Intuition

To handle any characters including delimiters and lengths, use an escaping mechanism or standard Base64 encoding. Alternatively, use a fixed-width length prefix (e.g., 4 bytes) for true binary safety.

⏱ O(N)💾 O(N)

Detailed Dry Run

Input: ["3#a", "b"] Encoding: Escape # as ##. Use # as delimiter. Result: "3##a#b#" Decoding: Unescape ## back to #.

java
public class Codec {
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for (String s : strs) {
            sb.append(s.replace("#", "##")).append(" # ");
        }
        return sb.toString();
    }
    public List<String> decode(String s) {
        List<String> res = new ArrayList<>();
        String[] parts = s.split(" # ", -1);
        for (int i=0; i<parts.length-1; i++) res.add(parts[i].replace("##", "#"));
        return res;
    }
}
← Previous QuestionValid Sudoku
Next Question →Brick Wall