leetcode：271.字符串的编码与解码_leetcode271

题目来源

• leetcode：271-VIP.字符串的编码与解码
• leetcode：659 · 编码和解码字符串

题目描述

请你设计一个算法，可以将一个字符串列表编码成一个字符串。这个编码后的字符串是可以通过网络进行高效传送的，并且可以在接收端被解码回原来的字符串列表。

1 号机（发送方）有如下函数：

string encode(vector<string> strs) {
  // ... your code
  return encoded_string;
}
1
2
3
4

2 号机（接收方）有如下函数：

vector<string> decode(string s) {
  //... your code
  return strs;
}
1
2
3
4

1 号机（发送方）执行：

string encoded_string = encode(strs);
1

2 号机（接收方）执行：

vector<string> strs2 = decode(encoded_string);
1

此时，2 号机（接收方）的 strs2 需要和 1 号机（发送方）的 strs 相同。
请你来实现这个 encode 和 decode 方法。

注意：

• 因为字符串可能会包含 256 个合法 ascii 字符中的任何字符，所以您的算法必须要能够处理任何可能会出现的字符。
• 请勿使用 “类成员”、“全局变量” 或 “静态变量” 来存储这些状态，您的编码和解码算法应该是非状态依赖的。
• 请不要依赖任何方法库，例如 eval 又或者是 serialize 之类的方法。本题的宗旨是需要您自己实现 “编码” 和 “解码” 算法。

题目解析

题目目的：

• 这道题让我们给字符串编码然后解码，然后题目中没有限制编码的方法，那么只要能成功的把编码/解码就可以了。
• 由于需要把一个字符串集变成一个字符串，然后把这个字符串再还原成原来的字符串集

思路：

• 最开始的想法是能不能在每一个字符串中间加个空格把它们连起来，然后再按照空格来隔开
• 但是这种方法的问题是：如果原来的一个字符串中就有空格，那么还原的时候就会被分隔成两个字符串，所以必须还加上长度的信息
• 编码方法：长度 + “/” + 字符串，比如对于 “a”,“ab”,“abc”，就变成 “1/a2/ab3/abc”，
• 因此，解码方法：先寻找 “/”，然后之前的就是要取出的字符个数，从 “/” 后取出相应个数即可，以此类推直至没有 "/"了

class Codec {
public:
    std::string encode(std::vector<std::string> & strs){
        std::string res ;
        for(auto &str : strs){
            res.append(std::to_string(str.size())).append("/").append(str);
        }
        return res;
    }
    
    std::vector<std::string> decode(std::string s){
        std::vector<std::string>res;
        int i = 0, size = s.size();
        while (i < size){
            int found = s.find('/', i);
            int len = stoi(s.substr(i, found - i));
            res.push_back(s.substr(found + i, len));
            i = found + len + 1;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

上面我们用一个变量i来记录当前遍历到的位置，我们也可以通过修改s，将已经解码的字符串删除，最终s变为空的时候停止循环，如下：

class Codec {
public:
    std::string encode(std::vector<std::string> & strs){
        std::string res ;
        for(auto &str : strs){
            res.append(std::to_string(str.size())).append("/").append(str);
        }
        return res;
    }

    std::vector<std::string> decode(std::string s){
        std::vector<std::string>res;
        int i = 0, size = s.size();
        while (!s.empty()){
            int found = s.find('/');
            int len = stoi(s.substr(0, found));
            s = s.substr(found + 1);
            res.push_back(s.substr(0, len));
            s = s.substr(len);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

我们还可以使用更简单的压缩方法，比如在每个字符串的后面加上换行字符 ‘\0’，其还属于一个字符串，这样在解码的时候，只要去查找这个换行字符就可以了，参见代码如下：

class Codec {
public:
    std::string encode(std::vector<std::string> & strs){
        string res;
        for (string str : strs) res += str + '\0';
        return res;
    }

    std::vector<std::string> decode(std::string s){
        std::vector<std::string>res;
        std::stringstream ss(s);
        std::string t;
        while (getline(ss, t, '\0')){
            res.push_back(t);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18