MediumNo. 0271LeetCode Premium

Encode and Decode Strings — LeetCode 271 Python Solution

Pattern
Hash Map
Topics
Design, Array, String
On study lists
Blind 75 and NeetCode 150
Reading time
4 min
Source
leetcode.com

The problem

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.

Example

Example
string encode(vector<string> strs) {
  // ... your code
  return encoded_string;
}

Python solution

PythonSolution
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

Time
O(n)
Space · auxiliary
O(1) to O(n)

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 271. Encode and Decode Strings is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0068Text JustificationHard
0722Remove CommentsMedium
0806Number of Lines To Write StringEasy
0900RLE IteratorMedium
0944Delete Columns to Make SortedEasy
1324Print Words VerticallyMedium

Frequently asked questions

How hard is LeetCode 271. Encode and Decode Strings?

LeetCode 271. Encode and Decode Strings is rated Medium on LeetCode.

What topics does LeetCode 271. Encode and Decode Strings cover?

LeetCode 271. Encode and Decode Strings is tagged Design, Array and String on LeetCode.

Is LeetCode 271. Encode and Decode Strings a premium problem?

Yes. LeetCode 271. Encode and Decode Strings is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Download for MacDownload for Windows

Free to download. Check it runs on your machine, then pick a plan.