[LeetCode] 271. Encode and Decode Strings

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 <= 200
0 <= strs[i].length <= 200
strs[i] contains any possible characters out of 256 valid ASCII characters.

Follow up: Could you write a generalized algorithm to work on any possible set of characters?

字符串的编码与解码。

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

思路

对于 input 给的字符串列表，我们可以把他压缩成这种形式

单词长度size + ‘,’ + 单词

那么对于一个单词列表 [hello, world, hello, world] 而言，他将会被压缩成这个样子。

5,hello5,world5,hello5,world

所以当我们试着再把这个字符串变回 字符串列表 的时候，我们可以用 string.indexOf(‘,’) 找到每一个逗号的位置，找到逗号之后，当前位置到逗号 [i, comma) 就是单词的长度 size，[comma + 1, comma + 1 + size) 则是单词本身。

复杂度

时间O(n)
空间O(n)

代码

Java实现

public class Codec {

    // Encodes a list of strings to a single string.
    // hello,world,hello,world
    // 5,hello5,world5,hello5,world
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for (String word : strs) {
            int size = word.length();
            sb.append(size).append(',').append(word);
        }
        return sb.toString();
    }

    // Decodes a single string to a list of strings.
    // hello,world,hello,world
    public List<String> decode(String s) {
        List<String> res = new ArrayList<>();
        int i = 0;
        while (i < s.length()) {
            int comma = s.indexOf(',', i);
            int size = Integer.valueOf(s.substring(i, comma));
            res.add(s.substring(comma + 1, comma + 1 + size));
            i = comma + 1 + size;
        }
        return res;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(strs));

JavaScript实现

/**
 * Encodes a list of strings to a single string.
 *
 * @param {string[]} strs
 * @return {string}
 */
var encode = function (strs) {
    let sb = [];
    for (let str of strs) {
        sb.push(str.length);
        sb.push('/');
        sb.push(str);
    }
    return sb.join('');
};

/**
 * Decodes a single string to a list of strings.
 *
 * @param {string} s
 * @return {string[]}
 */
var decode = function (s) {
    let res = [];
    let i = 0;
    while (i < s.length) {
        let slash = s.indexOf('/', i);
        let len = parseInt(s.substring(i, slash));
        let str = s.substring(slash + 1, slash + 1 + len);
        res.push(str);
        i = slash + 1 + len;
    }
    return res;
};

/**
 * Your functions will be called as such:
 * decode(encode(strs));
 */

相关题目

38. Count and Say
271. Encode and Decode Strings
443. String Compression
604. Design Compressed String Iterator
1313. Decompress Run-Length Encoded List