# 271. Encode and Decode Strings

## Description

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.

Machine 1 (sender) has the function:

string encode(vector<string> strs) {
return encoded_string;
}

Machine 2 (receiver) has the function:

vector<string> decode(string s) {
return strs;
}


So Machine 1 does:

string encoded_string = encode(strs);


and Machine 2 does:

vector<string> strs2 = decode(encoded_string);


strs2 in Machine 2 should be the same as strs in Machine 1.

Implement the encode and decode methods.

You are not allowed to solve the problem using any serialize methods (such as eval).

Example 1:

Input: dummy_input = ["Hello","World"]
Output: ["Hello","World"]
Explanation:
Machine 1:
Codec encoder = new Codec();
String msg = encoder.encode(strs);
Machine 1 ---msg---> Machine 2

Machine 2:
Codec decoder = new Codec();
String[] strs = decoder.decode(msg);


Example 2:

Input: dummy_input = [""]
Output: [""]


Constraints:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] contains any possible characters out of 256 valid ASCII characters.

Follow up: Could you write a generalized algorithm to work on any possible set of characters?

## Solutions

This is a typical example of a problem that involves serializing and deserializing data, which is a common requirement for storing or transmitting data (e.g., over a network).

### Method Overview

• encode(self, strs: List[str]) -> str: Converts a list of strings into a single string that includes both the length of each original string and the string itself. This is done to ensure that the original list can be accurately reconstructed later.

• decode(self, s: str) -> List[str]: Reverses the encoding process to reconstruct the original list of strings from the encoded single string.

### Detailed Explanation

#### Encoding Process

1. For each string in the input list, the length of the string is determined and formatted as a 4-character string. This fixed width is crucial for the decoding process, as it provides a consistent way to determine where each original string’s length ends and where the string itself begins in the encoded form.

2. The 4-character length is then concatenated with the actual string, and this combined string is added to a list (ans).

3. Finally, all combined strings in the list ans are joined together into a single string without any delimiter (since the length of each string is encoded at the beginning of each segment), and this string is returned.

Example: Encoding ["hello", "world"] results in '0005hello0005world'.

#### Decoding Process

1. The encoded string is processed from the beginning (i = 0) to the end (n = len(s)).

2. At each step, a 4-character substring is read and converted to an integer (size), representing the length of the next string in the encoded data.

3. The value of i is then advanced by 4 characters (past the length part), and a substring of length size is extracted, corresponding to one of the original strings.

4. This string is added to the result list ans, and i is advanced by size to move to the next segment of the encoded data.

5. This process repeats until the end of the encoded string is reached.

Example: Decoding '0005hello0005world' reconstructs the original list ["hello", "world"].

### Notes

• The choice of a 4-character length prefix assumes that the maximum length of any single string in the list does not exceed 9999 characters. If strings could be longer, the fixed width of the length prefix and the encoding/decoding logic would need to be adjusted accordingly.

• This approach is efficient and avoids potential issues with special characters or escape sequences that might occur if a delimiter-based approach were used.

• The comment in the code mentions a potential overflow issue if the size is larger than what can be represented by an int. However, in Python, integers can be arbitrarily large, so the practical concern would be the fixed width of the length encoding rather than integer overflow. The comment might be more relevant in languages with fixed-size integer types.

• public class Codec {

// Encodes a list of strings to a single string.
public String encode(List<String> strs) {
StringBuilder ans = new StringBuilder();
for (String s : strs) {
ans.append((char) s.length()).append(s);
}
return ans.toString();
}

// Decodes a single string to a list of strings.
public List<String> decode(String s) {
List<String> ans = new ArrayList<>();
int i = 0, n = s.length();
while (i < n) {
int size = s.charAt(i++);
i += size;
}
return ans;
}
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(strs));

• class Codec {
public:
// Encodes a list of strings to a single string.
string encode(vector<string>& strs) {
string ans;
for (string s : strs) {
int size = s.size();
ans += string((const char*) &size, sizeof(size));
ans += s;
}
return ans;
}

// Decodes a single string to a list of strings.
vector<string> decode(string s) {
vector<string> ans;
int i = 0, n = s.size();
int size = 0;
while (i < n) {
memcpy(&size, s.data() + i, sizeof(size));
i += sizeof(size);
ans.push_back(s.substr(i, size));
i += size;
}
return ans;
}
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.decode(codec.encode(strs));

• 
'''
>>> s = 'abcde'
>>> '{:4}'.format(len(s)) + s
'   5abcde'
>>>
>>> '{:4}'.format(333)
' 333'
>>>
>>> '{:4}'.format(1234)
'1234'
>>> '{:4}'.format(12345)
'12345'

>>> '{0:4}'.format(12345)
'12345'
>>> '{1:4}'.format(12345)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
IndexError: Replacement index 1 out of range for positional args tuple
>>> '{1:4}'.format(12345, 678910)
'678910'
>>> '{:4}'.format(12345, 678910)
'12345'
>>> '{0:4}'.format(12345, 678910)
'12345'
'''
class Codec: # no splitter
def encode(self, strs: List[str]) -> str:
"""Encodes a list of strings to a single string."""
ans = []
for s in strs:
ans.append('{:4}'.format(len(s)) + s)
return ''.join(ans)

def decode(self, s: str) -> List[str]:
"""Decodes a single string to a list of strings."""
ans = []
i, n = 0, len(s)
while i < n:
size = int(s[i : i + 4]) # so here potential overflow, if larger than int-max, need to clarify assumption with interviewer
i += 4
ans.append(s[i : i + size]) # note: exclusive for right index
i += size
return ans

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.decode(codec.encode(strs))

#########

class Codec:
def encode(self, strs: List[str]) -> str:
encoded = ""
for s in strs:
# cover for input: ["abcd", "####"]
encoded += str(len(s)) + "#" + s.replace("#", "$$") + "#" return encoded def decode(self, s: str) -> List[str]: decoded = [] i = 0 while i < len(s): j = s.find("#", i) length = int(s[i:j]) decoded.append(s[j+1:j+1+length].replace("$$", "#"))
i = j + 1 + length + 1

return decoded

############

class Codec: # wrong compared with above, for input: ["abcd", "####"]
def encode(self, strs):
encoded = ""
for s in strs:
encoded += str(len(s)) + "#" + s
return encoded

def decode(self, s):
decoded = []
i = 0
while i < len(s):
delimiter = s.index("#", i)
length = int(s[i:delimiter])
decoded.append(s[delimiter+1 :delimiter+1+length])
i = delimiter + 1 + length
return decoded


• type Codec struct {
}

// Encodes a list of strings to a single string.
func (codec *Codec) Encode(strs []string) string {
ans := &bytes.Buffer{}
for _, s := range strs {
t := fmt.Sprintf("%04d", len(s))
ans.WriteString(t)
ans.WriteString(s)
}
return ans.String()
}

// Decodes a single string to a list of strings.
func (codec *Codec) Decode(strs string) []string {
ans := []string{}
i, n := 0, len(strs)
for i < n {
t := strs[i : i+4]
i += 4
size, _ := strconv.Atoi(t)
ans = append(ans, strs[i:i+size])
i += size
}
return ans
}

// Your Codec object will be instantiated and called as such:
// var codec Codec
// codec.Decode(codec.Encode(strs));