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.
You are not allowed to solve the problem using any serialize methods (such as eval).
Example 1:
Input: dummy_input = ["Hello","World"] Output: ["Hello","World"] Explanation: Machine 1: Codec encoder = new Codec(); String msg = encoder.encode(strs); Machine 1 ---msg---> Machine 2 Machine 2: Codec decoder = new Codec(); String[] strs = decoder.decode(msg);
Example 2:
Input: dummy_input = [""] Output: [""]
Constraints:
1 <= strs.length <= 2000 <= strs[i].length <= 200strs[i]contains any possible characters out of256valid ASCII characters.
Follow up: Could you write a generalized algorithm to work on any possible set of characters?
Explanation
This is not a difficult problem, but it is a really great exercise.
After solving this problem, you will immediately understand how to encode strings into a single string and decode them again. There are some clever approaches but we will look at a general and typical approach.
Escape charater is our key to solve this problem. You have already seen and used escape characters. We use it to put some special meanings. For example, “\n” means you change the line. “\t” means you give a tab.
So, to encode separated strings into one string, we need some special character so that we can decode the string back into individual strings. You can choose any special character as a separator, but here, let’s say “/:” is a separator.
If we encode “abc” and “def”, it will be like this: “abc/:def”.
As we can easily see, the string can be separated into “abc” and “def”. However, this is not the end.
What if “/:” can’t work as a separator? “/:” it self can be part of a string. To solve this, we need to use escape character. Therefore, the string “/:” becomes “//:” when it is not a separator. So, if an encoded string looks like “a//:”, we know that it was originally “a/:”.
Easy, right? Let’s see the real implementation in Golang and Python.
class Codec:
def encode(self, strs: List[str]) -> str:
"""Encodes a list of strings to a single string.
"""
for i, s in enumerate(strs):
strs[i] = s.replace("/", "//")
return "/:".join(strs)
def decode(self, s: str) -> List[str]:
"""Decodes a single string to a list of strings.
"""
print(s)
is_slash = False
cur_str = ""
res = []
for c in s:
# print(c)
# print("cur_str: ",cur_str)
if c == "/":
if is_slash:
is_slash = False
else:
is_slash = True
cur_str = cur_str + c
elif c == ":":
if is_slash:
cur_str = cur_str[:len(cur_str) -1]
res.append(cur_str)
cur_str = ""
is_slash = False
else:
cur_str = cur_str + c
is_slash = False
else:
cur_str = cur_str + c
is_slash = False
res.append(cur_str)
return restype Codec struct {
}
// Encodes a list of strings to a single string.
func (codec *Codec) Encode(strs []string) string {
for i, str := range strs {
strs[i] = strings.ReplaceAll(str, "/", "//")
}
return strings.Join(strs, "/:")
}
// Decodes a single string to a list of strings.
func (codec *Codec) Decode(strs string) []string {
isSlash := false
var res []string
curStr := ""
for _, c := range strs {
if c == '/' {
if isSlash {
isSlash = false
continue
} else {
isSlash = true
}
curStr = curStr + string(c)
} else if c == ':' {
if isSlash {
res = append(res, curStr[:len(curStr)-1])
isSlash = false
curStr = ""
} else {
curStr = curStr + string(c)
}
} else {
isSlash = false
curStr = curStr + string(c)
}
}
res = append(res, curStr)
return res
}
As we encode, we insert “/:’ between strings and replace “/” into “//” so that we can detect that the slash is not a separator.
When we decode a string, we carefully detect “/:” and separate it into individual strings.
I highly recommend you try solving this yourself. It will be a great exercise. Happy coding!
Leave a Reply