Approach

Encode and Decode Strings

Problem

Design an algorithm to encode a list of strings to a single string. The encoded string is then decoded back to the original list of strings.

Implement encode and decode.

Example:

Input: strs = ["hello","world"]
Output: ["hello","world"]

Explanation:
encode: "5#hello5#world"
decode: "5#hello5#world" -> ["hello","world"]

Constraints:

Strings can contain any characters including delimiters
Must handle empty strings
Must be able to distinguish between different strings

Approach: Length Prefix with Delimiter

Intuition

The challenge is handling strings that may contain any character, including common delimiters like ,, :, etc. The solution is to prefix each string with its length and a delimiter that cannot be part of the length.

Key Insight

Format: length#string

Example: "hello" becomes "5#hello"
Empty string "" becomes "0#"
String with delimiter: "a#b" becomes "3#a#b"

Why This Works

Length tells us exactly how many characters to read
The # separator distinguishes length from content
Content can contain any character (even #)

Encoding Algorithm

def encode(strs):
    result = ""
    for s in strs:
        result += str(len(s)) + "#" + s
    return result

Decoding Algorithm

def decode(s):
    result = []
    i = 0
    while i < len(s):
        # Find the delimiter
        j = i
        while s[j] != '#':
            j += 1
        
        # Extract length
        length = int(s[i:j])
        
        # Extract string
        string = s[j + 1 : j + 1 + length]
        result.append(string)
        
        # Move to next encoding
        i = j + 1 + length
    
    return result

Time Complexity

Encode: O(n) where n is total characters across all strings
Decode: O(n) where n is length of encoded string

Space Complexity

O(n) for the result string

Alternative Approaches

1. Escape Character Approach

Use escape sequences for special characters. More complex and error-prone.

2. Fixed-Width Length Prefix

Use fixed number of digits for length (e.g., always 4 digits). Limits string length but simpler parsing.

3. Non-ASCII Delimiter

Use a character that's guaranteed not to appear in input. Not always possible.

Solution

java

1/**
2 * Encode and Decode Strings
3 * Time: O(n) for both encode and decode
4 * Space: O(n)
5 */
6
7import java.util.*;
8
9// Approach 1: Length Prefix with # Delimiter (Optimal)
10public class Codec {
11    // Encodes a list of strings to a single string.
12    public String encode(List<String> strs) {
13        StringBuilder result = new StringBuilder();
14        for (String s : strs) {
15            // Format: length + '#' + string
16            result.append(s.length()).append('#').append(s);
17        }
18        return result.toString();
19    }
20
21    // Decodes a single string to a list of strings.
22    public List<String> decode(String s) {
23        List<String> result = new ArrayList<>();
24        int i = 0;
25        
26        while (i < s.length()) {
27            // Find the delimiter '#'
28            int j = i;
29            while (s.charAt(j) != '#') {
30                j++;
31            }
32            
33            // Extract length
34            int length = Integer.parseInt(s.substring(i, j));
35            
36            // Extract string of given length
37            String str = s.substring(j + 1, j + 1 + length);
38            result.add(str);
39            
40            // Move to next encoded string
41            i = j + 1 + length;
42        }
43        
44        return result;
45    }
46}
47
48// Approach 2: Escape Character
49class Codec2 {
50    public String encode(List<String> strs) {
51        StringBuilder sb = new StringBuilder();
52        for (String s : strs) {
53            // Escape backslash and semicolon
54            sb.append(s.replace("\\", "\\\\").replace(";", "\;"));
55            sb.append(";");
56        }
57        return sb.toString();
58    }
59
60    public List<String> decode(String s) {
61        List<String> result = new ArrayList<>();
62        StringBuilder current = new StringBuilder();
63        
64        for (int i = 0; i < s.length(); i++) {
65            if (s.charAt(i) == '\\' && i + 1 < s.length()) {
66                // Escaped character
67                current.append(s.charAt(i + 1));
68                i++;
69            } else if (s.charAt(i) == ';') {
70                // End of string
71                result.add(current.toString());
72                current = new StringBuilder();
73            } else {
74                current.append(s.charAt(i));
75            }
76        }
77        
78        return result;
79    }
80}
81
82// Usage:
83// Codec codec = new Codec();
84// String encoded = codec.encode(Arrays.asList("hello", "world"));
85// List<String> decoded = codec.decode(encoded);
86