Leetcode #271: Encode and Decode Strings
In this guide, we solve Leetcode #271 Encode and Decode Strings in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
Problem Statement
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.
Quick Facts
- Difficulty: Medium
- Premium: Yes
- Tags: Design, Array, String
Intuition
We need to scan characters while tracking positions or counts.
A simple state machine keeps the logic precise.
Approach
Iterate through the string once and update the state for each character.
Use a map or array if you need fast lookups.
Steps:
- Iterate through characters.
- Maintain necessary state.
- Build or validate the output.
Example
string encode(vector<string> strs) {
// ... your code
return encoded_string;
}
Python Solution
class Codec:
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])
i += 4
ans.append(s[i : i + size])
i += size
return ans
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.decode(codec.encode(strs))
Complexity
The time complexity is . The space complexity is O(1) to O(n).
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.