Leetcode 271. Encode and Decode Strings

Problem Explanation and Approach

In this problem, we are asked to write two methods - encode and decode. encode method will take a list of strings and encode it into a single string while the decode method will reverse the process and get the original list of strings from the encoded input.

To encode the strings, we can concatenate the length of each string, a separator, and the string itself. This "length" + "/" + "string" will be repeated for each string in the input list. It will create a single large encoded string.

1
2
3For example if we have strings like 
4"abc", "defg", "hi"
5The encoded string will be 
63/abc4/defg2/hi
7Here 3, 4, and 2 are lengths of the strings and "/" is separator.

And for decoding, we will search for the separator ("/"), get the length of the string from the start of the sub-string to the separator, then move the string pointer to the end of this string which is the "length"+"separator".

1
2
3According to the previous example, when we decode
4"3/abc4/defg2/hi"
5We first find "/", get "3" which is length of "abc". 
6Then we move 4 positions (3 positions of string length + 1 position of "/") from the "/". Then we get the next string.
7Repeating this process will give us the original strings.

This approach enables us to encode and decode any list of strings containing any valid ASCII character.

Python Solution

1
2python
3class Solution:
4    def encode(self, strs):
5        encoded = ""
6        for s in strs:
7            encoded += str(len(s)) + '/' + s
8        return encoded
9        
10    
11    def decode(self, s):
12        strs = []
13        i = 0
14        while i < len(s):
15            # identify the position of '/'
16            slash = s.find('/', i)
17            # the length of the string is the characters from index `i` till the position of '/'
18            length = int(s[i:slash])
19            # reposition `i` to point to the start of next string
20            i = slash + length + 1
21            # push the string into the result
22            strs.append(s[slash + 1:i])
23            
24        return strs

Java Solution

1
2java
3public class Solution {
4    // Encodes a list of strings to a single string.
5    public String encode(List<String> strs) {
6        StringBuilder sb = new StringBuilder();
7        for(String str : strs)
8            sb.append(str.length()).append('/').append(str);
9        return sb.toString();
10    }
11
12    // Decodes a single string to a list of strings.
13    public List<String> decode(String s) {
14        List<String> strs = new ArrayList<>();
15        int i = 0, len = s.length();
16        while(i < len) {
17            int slash = s.indexOf('/', i);
18            int size = Integer.valueOf(s.substring(i, slash));
19            i = slash + size + 1;
20            strs.add(s.substring(slash + 1, i));
21        }
22        return strs;
23    }
24}

Javascript Solution

1
2javascript
3class Solution {
4    encode(strs) {
5        let encoded = "";
6        for(let str of strs) {
7            encoded += str.length + "/" + str;
8        }
9        return encoded;
10    }
11    
12    decode(s) {
13        let strs = [];
14        let i = 0;
15        while(i < s.length) {
16            let slash = s.indexOf('/', i);
17            let len = Number(s.substring(i, slash));
18            i = slash + len + 1;
19            strs.push(s.substring(slash + 1, i));
20        }
21        return strs;
22    }
23}

C++ Solution

1
2c++
3class Solution {
4public:
5
6    // Encodes a list of strings to a single string.
7    string encode(vector<string>& strs) {
8        string encoded;
9        for (string& str : strs)
10            encoded += to_string(str.size()) + '/' + str;
11        return encoded;
12    }
13
14    // Decodes a single string to a list of strings.
15    vector<string> decode(string s) {
16        vector<string> strs;
17        for (int i = 0; i < s.size();) {
18            const int slash = s.find('/', i);
19            const int len = stoi(s.substr(i, slash - i));
20            i = slash + len + 1;
21            strs.push_back(s.substr(slash + 1, len));
22        }
23        return strs;
24    }
25};

C# Solution

1
2csharp
3public class Solution {
4    // Encodes a list of strings to a single string.
5    public string Encode(List<string> strs) {
6        StringBuilder sb = new StringBuilder();
7        foreach(string str in strs)
8            sb.Append(str.Length).Append('/').Append(str);
9        return sb.ToString();
10    }
11
12    // Decodes a single string to a list of strings.
13    public List<string> Decode(string s) {
14        List<string> strs = new List<string>();
15        int i = 0;
16        while(i < s.Length) {
17            int slash = s.IndexOf('/', i);
18            int size = Int32.Parse(s.Substring(i, slash - i));
19            i = slash + size + 1;
20            strs.Add(s.Substring(slash + 1, size));
21        }
22        return strs;
23    }
24}

Swift Solution

1
2swift
3class Solution {
4    func encode(_ strs: [String]) -> String {
5        var encoded = ""
6        for str in strs {
7            encoded += "\(str.count)/" + str
8        }
9        return encoded
10    }
11
12    func decode(_ s: String) -> [String] {
13        var strs = [String]()
14        var i = 0
15        while i < s.count {
16            if let slash = s.index(of: "/"), let len = Int(s[s.startIndex..<slash]) {
17                i = slash.encodedOffset + len + 1
18                let str = s[s.index(slash, offsetBy: 1)...s.index(s.startIndex, offsetBy: i-1)]
19                strs.append(String(str))
20            }
21        }
22        return strs
23    }
24}

PHP Solution

1
2php
3class Solution {
4    function encode($strs) {
5        $encoded = "";
6        foreach($strs as $str) {
7            $encoded .= strlen($str)."/".$str;
8        }
9        return $encoded;
10    }
11
12    function decode($s) {
13        $strs = array();
14        $i = 0;
15        while($i < strlen($s)) {
16            $slash = strpos($s, "/", $i);
17            $len = substr($s, $i, $slash - $i);
18            $i = $slash + $len + 1;
19            array_push($strs, substr($s, $slash + 1, $len));
20        }
21        return $strs;
22    }
23}

Ruby Solution

1
2ruby
3class Solution
4    def encode(strs)
5        encoded = ""
6        strs.each { |str| encoded += "#{str.length}/#{str}" }
7        encoded
8    end
9
10    def decode(s)
11        strs = []
12        i = 0
13        while i < s.length
14            slash = s.index('/', i)
15            len = s.slice(i, slash).to_i
16            i = slash + len + 1
17            strs += [s.slice(slash+1, len)]
18        end
19        strs
20    end
21end

All the programming solutions follow the same method for encoding and decoding the strings. Only the syntax varies according to the programming language. These solutions work for all scenarios as they use a defined encoding and decoding pattern.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫