Watch 10 video solutions for Encode and Decode Strings, a medium level problem involving Array, String, Design. This walkthrough by NeetCode has 333,550 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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) {
// ... your code
return encoded_string;
}
Machine 2 (receiver) has the function:
vector<string> decode(string s) {
//... your code
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 <= 2000 <= strs[i].length <= 200strs[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?
Problem Overview: You need to design two functions: encode converts a list of strings into a single string, and decode reconstructs the original list from that encoded string. The tricky part is preserving boundaries between strings without losing information, even when the strings contain special characters.
Approach 1: Delimiter-Based Encoding (O(n) time, O(n) space)
A straightforward idea is to join all strings using a delimiter such as # or |. During decoding, split the encoded string by that delimiter. The problem appears when original strings themselves contain the delimiter. You would need an escaping mechanism (for example replacing # with ##) before encoding and reversing the process during decoding. This works but adds extra processing logic and edge cases.
Approach 2: Length-Prefix Encoding (O(n) time, O(n) space)
The robust solution stores the length of each string before the string itself. For every word s, append len(s), a separator (commonly #), and the string. Example: ["leet","code"] becomes 4#leet4#code. During decoding, iterate through the encoded string, read characters until the separator to determine the length, convert it to an integer, then extract the next length characters as the original string. Repeat until the string ends.
This approach works regardless of the content of the strings because the boundary is defined by length rather than a special character. The decoding process simply scans the string, parses the numeric prefix, and slices the substring accordingly. Every character is processed once, giving linear complexity.
The technique is essentially a small protocol design problem, which is why the problem is tagged under design. The implementation mainly uses sequential traversal of a string and storage in a dynamic list or array.
Recommended for interviews: Length-prefix encoding is the expected answer. It avoids delimiter conflicts and guarantees correct decoding in O(n) time. Mentioning the delimiter idea first shows you considered simpler designs, but implementing the length-prefix protocol demonstrates stronger problem-solving and system design thinking.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Delimiter-Based Encoding | O(n) | O(n) | Quick prototype when input is guaranteed not to contain the delimiter or when escaping is acceptable |
| Length-Prefix Encoding | O(n) | O(n) | General case solution that works for any characters in the input strings |