Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/271.html
271. Encode and Decode Strings
Level
Medium
Description
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.
Machine 1 (sender) has the function:
string encode(vector<string> strs) {
// ... your code
return encoded_string;
}
Machine 2 (receiver) has the function:
vector<string> decode(string s) {
//... your code
return strs;
}
So Machine 1 does:
string encoded_string = encode(strs);
and Machine 2 does:
vector<string> strs2 = decode(encoded_string);
strs2
in Machine 2 should be the same as strs
in Machine 1.
Implement the encode
and decode
methods.
Note:
- The string may contain any possible characters out of 256 valid ascii characters. Your algorithm should be generalized enough to work on any possible characters.
- Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless.
- Do not rely on any library method such as
eval
or serialize methods. You should implement your own encode/decode algorithm.
Solution
In encode()
method, store each string’s length so that the strings can be uniquely determined. For each string str
in strs
, encode it as the following format: str.length() + "/" + str
.
- For example, “encode” is encoded as
6/encode
. All strings’ encoding results are concatenated together.
In decode()
method, each time find the first index of "/"
, and the substring before "/"
is an integer that represents the length of the next string. Convert the substring before "/"
into an integer, obtain the substring with the determined length just after "/"
, and add the substring after "/"
to the result list. After one string is decoded, continue with the remaining strings. Finally, return the result list.
You can also use a simpler compression method, add a newline character \0
at the end of each string, which also belongs to a string, so when decoding, just look for the newline character.
Code
-
import org.apache.commons.io.IOUtils; import java.io.IOException; import java.io.StringReader; import java.util.LinkedList; import java.util.List; public class Encode_and_Decode_Strings { public class Codec { // Encodes a list of strings to a single string. public String encode(List<String> strs) { String res = ""; for (String str : strs) res += str + '\0'; return res; } // Decodes a single string to a list of strings. public List<String> decode(String s) throws IOException { return IOUtils.readLines(new StringReader(s)); } } public class Codec_2nd_solution { // Encodes a list of strings to a single string. public String encode(List<String> strs) { StringBuffer sb = new StringBuffer(); int size = strs.size(); for (int i = 0; i < size; i++) { String str = strs.get(i); int length = str.length(); sb.append(length + "/" + str); } return sb.toString(); } // Decodes a single string to a list of strings. public List<String> decode(String s) { List<String> list = new ArrayList<String>(); StringBuffer sb = new StringBuffer(s); int endIndex = 0; while (endIndex < s.length()) { int index = sb.toString().indexOf('/', endIndex); // @note: first `/` after index i int length = Integer.parseInt(sb.substring(endIndex, index)); endIndex = index + length + 1; String str = sb.substring(index + 1, endIndex); list.add(str); } return list; } } // Your Codec object will be instantiated and called as such: // Codec codec = new Codec(); // codec.decode(codec.encode(strs)); // Your Codec object will be instantiated and called as such: // Codec codec = new Codec(); // codec.decode(codec.encode(strs)); } ############ public class Codec { // Encodes a list of strings to a single string. public String encode(List<String> strs) { StringBuilder ans = new StringBuilder(); for (String s : strs) { ans.append((char) s.length()).append(s); } return ans.toString(); } // Decodes a single string to a list of strings. public List<String> decode(String s) { List<String> ans = new ArrayList<>(); int i = 0, n = s.length(); while (i < n) { int size = s.charAt(i++); ans.add(s.substring(i, i + size)); i += size; } return ans; } } // Your Codec object will be instantiated and called as such: // Codec codec = new Codec(); // codec.decode(codec.encode(strs));
-
// OJ: https://leetcode.com/problems/encode-and-decode-strings/ // Time: O(N) // Space: O(1) class Codec { public: string encode(vector<string>& strs) { string ans; for (string &str : strs) { for (char c : str) { if (c == '$') ans.push_back(c); ans.push_back(c); } ans.push_back('$'); ans.push_back('x'); } return ans; } vector<string> decode(string s) { vector<string> ans; int i = 0, N = s.size(); while (i < N) { string str; for (; i < N; ++i) { if (s[i] != '$') str.push_back(s[i]); else if (i + 1 < N && s[i + 1] == '$') str.push_back(s[i++]); else { i += 2; break; } } ans.push_back(str); } return ans; } };
-
class Codec: def encode(self, strs): encoded = "" for s in strs: encoded += str(len(s)) + "#" + s return encoded def decode(self, s): decoded = [] i = 0 while i < len(s): delimiter = s.index("#", i) length = int(s[i:delimiter]) decoded.append(s[delimiter+1 :delimiter+1+length]) i = delimiter + 1 + length return decoded ############ ''' >>> s = 'abcde' >>> '{:4}'.format(len(s)) + s ' 5abcde' >>> >>> '{:4}'.format(333) ' 333' >>> >>> '{:4}'.format(1234) '1234' >>> '{:4}'.format(12345) '12345' >>> '{0:4}'.format(12345) '12345' >>> '{1:4}'.format(12345) Traceback (most recent call last): File "<stdin>", line 1, in <module> IndexError: Replacement index 1 out of range for positional args tuple >>> '{1:4}'.format(12345, 678910) '678910' >>> '{:4}'.format(12345, 678910) '12345' >>> '{0:4}'.format(12345, 678910) '12345' ''' class Codec: # no splitter 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]) # so here potential overflow, if larger than int-max, need to clarify assumption with interviewer i += 4 ans.append(s[i : i + size]) # note: exclusive for right index i += size return ans # Your Codec object will be instantiated and called as such: # codec = Codec() # codec.decode(codec.encode(strs))
-
type Codec struct { } // Encodes a list of strings to a single string. func (codec *Codec) Encode(strs []string) string { ans := &bytes.Buffer{} for _, s := range strs { t := fmt.Sprintf("%04d", len(s)) ans.WriteString(t) ans.WriteString(s) } return ans.String() } // Decodes a single string to a list of strings. func (codec *Codec) Decode(strs string) []string { ans := []string{} i, n := 0, len(strs) for i < n { t := strs[i : i+4] i += 4 size, _ := strconv.Atoi(t) ans = append(ans, strs[i:i+size]) i += size } return ans } // Your Codec object will be instantiated and called as such: // var codec Codec // codec.Decode(codec.Encode(strs));