Problem
Design an algorithm to encode a list of strings to a single string and then decode that string back into the original list of strings.The encoding must preserve the boundaries between strings so that the original strings can be reconstructed correctly, even when they contain special characters.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
strs = ["hello", "world"]Encoded
5#hello5#worldDecoded
["hello", "world"]Solution
This solution uses Length Prefix Encoding. For each string, we store its length followed by a delimiter and then the actual string.For example,
"hello" becomes "5#hello". The length prefix tells us exactly how many characters belong to the current string. This makes the encoding safe even if the string itself contains the delimiter character.
During decoding, we first find the delimiter to determine the length of the next string. We then read exactly that many characters and add the extracted string to the result. We repeat this process until the entire encoded string has been processed.
public class Codec {
public String encode(List<String> strs) {
StringBuilder result = new StringBuilder();
for (String str : strs) {
result.append(str.length())
.append("#")
.append(str);
}
return result.toString();
}
public List<String> decode(String s) {
List<String> result = 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));
j++;
String str = s.substring(j, j + length);
result.add(str);
i = j + length;
}
return result;
}
}Complexity
During encoding, every character from every string is processed once. Therefore, the time complexity isO(n), where n is the total number of characters across all strings.
During decoding, every character in the encoded string is processed once, resulting in
O(n) time complexity.
The encoded string and decoded result require space proportional to the total input size, so the extra space complexity is
O(n).