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.