Encode And Decode Strings - Leetcode Solution

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.

Example:

Input: ["hello","world"] Output: "5#hello5#world"

Explanation: The input list of strings is encoded as a single string where '#' separates the length of the string and the actual string. So "hello" is represented as "5#hello" and "world" is represented as "5#world". The two strings are then concatenated to form the final encoded string "5#hello5#world".

Solution:

To solve this problem, we need to come up with an encoding scheme that allows us to represent each string in the input list as a single string. We can use the following encoding scheme:

1. For each string, we will represent it as "length of string#string". For example, the string "hello" can be represented as "5#hello".

2. To separate multiple encoded strings, we will use the "#" character.

Using this encoding scheme, we can encode each string in the input list as a single string and then concatenate all the encoded strings to form a single encoded string.

To decode the encoded string back to the original list of strings, we can use the following steps:

1. Initialize an empty list to store the decoded strings.

2. Split the encoded string into individual encoded strings using "#" as the separator.

3. For each encoded string, split it into the length and the actual string using "#" as the separator.

4. Convert the length from string to integer and extract the actual string.

5. Append the actual string to the decoded string list.

6. Return the decoded string list.

Let's take a look at the Python code for both encoding and decoding:

class Codec: def encode(self, strs: List[str]) -> str: encoded_strs = [] for s in strs: encoded_strs.append(str(len(s)) + "#" + s) return "".join(encoded_strs)

def decode(self, s: str) -> List[str]:
    decoded_strs = []
    i = 0
    while i < len(s):
        j = i
        while s[j] != "#":
            j += 1
        length = int(s[i:j])
        decoded_strs.append(s[j + 1:j + length + 1])
        i = j + length + 1
    return decoded_strs

In the encode function, we use a for loop to iterate over each string in the input list. For each string, we encode it and append the encoded string to a list. We then return the concatenated string formed by joining all the encoded strings together.

In the decode function, we use a while loop to iterate over each encoded string in the input string. We use a nested while loop to find the length of the encoded string by searching for the "#" character. Once we have the length, we extract the actual string and append it to a list. We then update the value of the loop variable i to the position of the next encoded string. Finally, we return the list of decoded strings.

Time Complexity:

The time complexity of both encoding and decoding functions is O(n), where n is the number of strings in the input list. This is because we need to iterate over each string in the input list and perform some constant-time operations for each string.

Space Complexity:

The space complexity of the encode function is O(n) because we need to store the encoded strings in a list. The space complexity of the decode function is also O(n) because we need to store the decoded strings in a list.

1class Codec {
2public:
3
4    // Encodes a list of strings to a single string.
5    string encode(vector<string>& strs) {
6        string encoded = "";
7        for (string& str : strs) {
8            encoded += to_string(str.size()) + '#' + str;
9        }
10        return encoded;
11    }
12
13    // Decodes a single string to a list of strings.
14    vector<string> decode(string s) {
15        vector<string> strs;
16        int i = 0;
17        while (i < s.size()) {
18            int index = s.find('#', i);
19            int len = stoi(s.substr(i, index - i));
20            strs.push_back(s.substr(index + 1, len));
21            i = index + len + 1;
22        }
23        return strs;
24    }
25};
26
27// Your Codec object will be instantiated and called as such:
28// Codec codec;
29// codec.decode(codec.encode(strs));