271. Encode and Decode Strings

MediumDesignArrayString

Problem Description

In this problem, we need to develop a method to encode and decode lists of strings so that they can be sent correctly over a network. The main challenge is to create a format for the encoded string that allows us to uniquely decipher each string in the list upon decoding without any ambiguity or loss of information. The encoded string must carry enough information to restore the original list of strings exactly.

Intuition

The intuition behind the solution is to prepend the length of each string to it before appending it to the encoded string, separating the length of the string from the string itself with a delimiter or using a fixed-width representation of the length. Upon decoding, we leverage the length information to extract each string accurately.

The chosen approach in the provided solution uses a fixed-width 4-character representation to store the length of each string. This approach simplifies the encoding and decoding process as follows:

Encoding: For each string in the input list, we determine its length and format it to a 4-character string with padding, if necessary. This length prefix is then concatenated with the actual string. Once all strings have been processed this way, they are joined together to form the final encoded string.
Decoding: To decode, we iterate over the encoded string, reading 4 characters at a time to determine the length of the next string. This length is converted to an integer, which is then used to extract the next string of that length from the encoded string. This process continues until the entire encoded string has been successfully decoded into the original list of strings.

The solution is clean and efficient as it avoids ambiguity (since the length prefix is fixed-width, there is no confusion about where each string starts and ends) and eschews the need for escape characters or complex parsing logic.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Linear SearchBinary SearchQuick SelectHash Set

I don’t know

Solution Approach

The implementation of the solution uses basic string manipulation and list operations to achieve the desired result. The codec class created consists of two methods: encode and decode.

Encode Method

The encode method takes a list of strings as input. For each string in the input list, it performs the following steps:

It calculates the length of the string.
It then formats this length into a 4-character wide string, using Python's .format() method. This is done by the expression '{:4}'.format(len(s)), which ensures that the length is padded with spaces if it is less than 4 characters long. The use of fixed-width for the length ensures the encoded string can be correctly parsed during decoding.
The 4-character length prefix is concatenated with the actual string.
These resulting strings are appended to an accumulator list ans.

After processing all the strings, the ans list is joined into a single string without any delimiter between them and returned. This works because the fixed-width length prefix allows us to know exactly where each string begins and ends.

Decode Method

The decode method is responsible for reversing the encoding process. It takes the encoded single string as input and outputs the original list of strings. The process is as follows:

Initialize an empty list ans to store the decoded strings, and set i = 0 to keep track of the current index in the encoded string, s.
While i is less than the length of s, perform the following steps in a loop: a. Read 4 characters from i to i + 4 to get the string's length. Convert it to an integer with int(s[i : i + 4]). Since we know the length of each string is exactly 4 characters, we can directly slice out the length information. b. Update i to skip past the length prefix. c. Use the length to determine the substring that constitutes our original string, found at s[i : i + size]. d. Append this substring to the ans list. e. Update i to move past the current string, preparing to read the length of the next string.

Once the loop is finished (and thus, the entire string s has been parsed), the ans list contains all the original strings in the correct order. The list ans is returned to provide the decoded list of strings.

These methods form an efficient and robust solution for the problem, making use of simple data structures (strings and lists) and straightforward algorithmic patterns (iteration and substring extraction based on a fixed format).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1dp[i] = dp[i] + dp[i - 1]dp[i] = (dp[i] + dp[j] + 1) for j in 0 to idp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don’t know

Example Walkthrough

Let's assume we have the following list of strings that we want to encode and then decode:

["hello", "world", "leetcode", "example"]

The encoding process for each string in this example would be as follows:

Take the first string "hello":
- Calculate the length: 5
- Format the length to 4-characters: ' 5'
- Concatenate the length and the string: ' 5hello'
Now for the second string "world":
- Calculate the length: 5
- Format the length to 4-characters: ' 5'
- Concatenate the length and the string: ' 5world'
Follow the same steps for "leetcode":
- Calculate the length: 8
- Format the length to 4-characters: ' 8'
- Concatenate the length and the string: ' 8leetcode'
And finally for "example":
- Calculate the length: 7
- Format the length to 4-characters: ' 7'
- Concatenate the length and the string: ' 7example'

After encoding all elements of the list, we join them together to form the final encoded string without any delimiter:

Encoded String: ' 5hello 5world 8leetcode 7example'

Now, for the decoding process, we start with the encoded string and decode it back into the original list of strings:

Initialize an empty list ans and set i = 0
While i < len(s): (where s is the encoded string) a. Read 4 characters to get the length: int(' 5') -> 5 b. Update i by 4: i = i + 4 c. Extract 5 characters starting from the new i: "hello" d. Append "hello" to ans e. Update i by 5 to move past the current string

Repeat steps a-e to decode the next strings:

For "world", extract 5 characters after reading the length -> ans becomes ["hello", "world"]
For "leetcode", extract 8 characters after reading the length -> ans becomes ["hello", "world", "leetcode"]
For "example", extract 7 characters after reading the length -> ans becomes ["hello", "world", "leetcode", "example"]

Once we reach the end of the encoded string, the decoding process is complete. The final decoded list of strings is:

Decoded List: ["hello", "world", "leetcode", "example"]

This walk-through demonstrates that our encoding scheme correctly maintains the integrity and order of the original list of strings when it is decoded back from the encoded string.

Solution Implementation

1class Codec:
2    def encode(self, strs: List[str]) -> str:
3        """
4        Encodes a list of strings to a single string.
5      
6        Each string is prefixed with its length in a 4-character wide field, 
7        allowing for easy extraction during decoding.
8        """
9        encoded_string = []
10        for string in strs:
11            # '{:4}' formats the length into a 4-character wide field, 
12            # padding with spaces if the number is less than 4 characters long.
13            length_prefix = '{:4}'.format(len(string))
14            encoded_string.append(length_prefix + string)
15        return ''.join(encoded_string)
16
17    def decode(self, s: str) -> List[str]:
18        """
19        Decodes a single string to a list of strings.
20      
21        Each string was encoded with a 4-character length prefix, which we use to 
22        determine where one string ends and the next begins.
23        """
24        decoded_strings = []
25        i = 0
26        n = len(s)
27        while i < n:
28            # Extract the length of the next string, which is stored in the first 4 characters.
29            size = int(s[i: i + 4])
30            i += 4
31            # Extract the string of the given length.
32            decoded_strings.append(s[i: i + size])
33            i += size
34        return decoded_strings
35
36
37# Example of how the Codec class is expected to be used:
38# codec = Codec()
39# encoded_data = codec.encode(strs)
40# decoded_data = codec.decode(encoded_data)
41

1import java.util.List;
2import java.util.ArrayList;
3
4public class Codec {
5
6    /**
7     * Encodes a list of strings to a single string.
8     *
9     * @param strs the list of strings to encode
10     * @return encoded single string
11     */
12    public String encode(List<String> strs) {
13        // Use StringBuilder to efficiently build the encoded string
14        StringBuilder encodedString = new StringBuilder();
15      
16        // Append the length of each string followed by the string itself to the builder
17        for (String str : strs) {
18            // Cast length to char to compactly store the length (only safe for strings of length 0-65535)
19            encodedString.append((char) str.length()).append(str);
20        }
21      
22        // Convert the StringBuilder to a String and return
23        return encodedString.toString();
24    }
25
26    /**
27     * Decodes a single string to a list of strings.
28     *
29     * @param s the encoded single string
30     * @return decoded list of strings
31     */
32    public List<String> decode(String s) {
33        // Create a list to hold the decoded strings
34        List<String> decodedStrings = new ArrayList<>();
35      
36        // Initialize an index to iterate through the encoded string
37        int index = 0;
38        int length = s.length();
39      
40        // Iterate through the encoded string and decode the strings
41        while (index < length) {
42            // Read the size of the next string
43            int size = s.charAt(index++);
44            // Extract the actual string by its size and add it to the collection
45            decodedStrings.add(s.substring(index, index + size));
46            // Move the index past the retrieved string
47            index += size;
48        }
49      
50        // Return the list of decoded strings
51        return decodedStrings;
52    }
53}
54
55/* Usage example:
56// Instantiate the codec
57Codec codec = new Codec();
58// Encode and decode
59List<String> strs = codec.decode(codec.encode(strs));
60*/
61

1#include <string>
2#include <vector>
3
4class Codec {
5public:
6    // Encodes a list of strings to a single string.
7    // Each string's length is stored as a fixed-size prefix before the actual string content.
8    string encode(const vector<string>& strs) {
9        string encodedString;
10      
11        for (const string& str : strs) {
12            // Convert the size to a string of bytes and append it to the result.
13            int size = str.size();
14            encodedString.append(reinterpret_cast<char*>(&size), sizeof(size));
15            // Append the actual string data.
16            encodedString.append(str);
17        }
18      
19        return encodedString;
20    }
21
22    // Decodes a single string to a list of strings by reading the fixed-size length prefix
23    // and then reading the corresponding number of characters.
24    vector<string> decode(const string& s) {
25        vector<string> decodedStrings;
26      
27        size_t i = 0;
28        int stringSize = 0;
29      
30        while (i < s.size()) {
31            // Copy the size information at the current position.
32            memcpy(&stringSize, s.data() + i, sizeof(stringSize));
33            i += sizeof(stringSize);
34          
35            // Get the substr starting from the current position with the extracted length
36            decodedStrings.push_back(s.substr(i, stringSize));
37            i += stringSize;
38        }
39      
40        return decodedStrings;
41    }
42};
43
44// The Codec object usage example:
45// Codec codec;
46// vector<string> strs = codec.decode(codec.encode(strs));
47

1// Encodes a list of strings to a single string.
2// Each string's length is stored as a fixed-size prefix before the actual string content.
3function encode(strs: string[]): string {
4    let encodedString = '';
5
6    for (const str of strs) {
7        // Convert the size to a 32-bit integer and add it to the result.
8        const size = str.length;
9        const buffer = new ArrayBuffer(4);
10        const view = new DataView(buffer);
11        view.setUint32(0, size);
12      
13        // Convert the ArrayBuffer to a string and append it to the result.
14        encodedString += String.fromCharCode.apply(null, new Uint8Array(buffer));
15        // Append the actual string data.
16        encodedString += str;
17    }
18
19    return encodedString;
20}
21
22// Decodes a single string to a list of strings by reading the fixed-size length prefix
23// and then reading the corresponding number of characters.
24function decode(s: string): string[] {
25    const decodedStrings: string[] = [];
26
27    let i = 0;
28  
29    while (i < s.length) {
30        // Create an ArrayBuffer and DataView representing the size of the next string.
31        const buffer = new ArrayBuffer(4);
32        const view = new DataView(buffer);
33      
34        // Convert the next 4 characters into the string size.
35        for (let j = 0; j < 4; j++) {
36            view.setUint8(j, s.charCodeAt(i + j));
37        }
38      
39        const stringSize = view.getUint32(0);
40        i += 4;
41      
42        // Get the substring starting from the current position with the extracted length
43        const str = s.substring(i, i + stringSize);
44        decodedStrings.push(str);
45        i += stringSize;
46    }
47
48    return decodedStrings;
49}
50
51// Usage example:
52// const encoded = encode(['hello', 'world']);
53// const decoded = decode(encoded);
54

Not Sure What to Study? Take the 2-min Quiz：

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right<, left, right<=, right, left<, right, left

I don’t know

Time and Space Complexity

Encode function:

Time Complexity: The encoding function iterates over all strings in the list, appending a 4-character length header to each string. The time complexity for appending operations in Python lists is O(1). Assuming the average length of strings is k, and there are n strings, the total time complexity will be O(nk) since it needs to process each character in each string.
Space Complexity: Space complexity for the encoding function would be O(nk) as well. This is due to the fact that it constructs a new string containing all of the individual strings with their 4-character headers. The output size is proportional to the total size of all input strings.

Decode function:

Time Complexity: For the decode function, a single pass through the encoded string is made, extracting the length of each string and then the string itself. With the same assumption for average string length k and n strings, the time complexity will be O(nk) because for each string, the function reads 4 characters for size and then k characters for the actual string.
Space Complexity: The decode function creates a list of strings resulting in the same O(nk) space complexity as for the encoding function, as it needs to store all the decoded strings in memory.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

271. Encode and Decode Strings

Problem Description

Intuition

Solution Approach

Encode Method

Decode Method

Example Walkthrough

Solution Implementation

Time and Space Complexity

Encode function:

Decode function: