聖地亞歌

Leetcode P0271 "Encode and Decode Strings" 题解

2021/07/09 Leetcode

博文中会简要介绍Leetcode P0271题目分析及解题思路。

“Encode and Decode Strings”是一道中等难度的题目，这道题利用到了分块编码的思想，这种思路来源于HTTP v1.1协议。

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).

解码算法基本上是编码算法的逆，所以这里重点讲解编码算法。

为什么会想到分块编码的思路？

由于给定的字符串数组可能包含任意ASCII码内的字符，所以如果用了某些ASCII码的字符来作为分隔符，很有可能会导致不能正确地还原原字符串数组。虽然可以使用Unicode中的某些字符来作为分隔符，但这样：一是不够通用，二是不够优雅。所以用分块编码的思路，在每个块的拼接之前插入一段编码。这个编码长度固定，易于后续解码的时候切割字符串，同时也用以记录后续插入的这个块的大小。

如何使得代表块大小的编码长度固定？

这同样要利用到编码的思想。由于字符串长度用整型int表示，所以题目中任意给定字符串的长度可以用4 bytes或者说32 bits来表示，而ASCII码的字符个数有256个，可以用8 bits来表示，所以我们可以将一个int数转化（切割）为4个ASCII码表示，即从10进制转换为了256进制。这样就能得到长度固定为4的编码。

基本思路

对给定的字符串数组的每个字符串统计出长度，并对长度编码成4个ASCII码，先插入长度编码，然后拼接该字符串。最后得到一个完整长串。而解码的思路，基本就是编码思路反过来。

img

以下是Java的题解代码实现。

public class Codec {
    // Encodes string length to bytes string
    public String intToString(String s) {
        int x = s.length();
        char[] bytes = new char[4];
        for(int i = 3; i > -1; --i) {
            bytes[3 - i] = (char) (x >> (i * 8) & 0xff);
        }
        return new String(bytes);
    }

    // Encodes a list of strings to a single string.
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for(String s: strs) {
            sb.append(intToString(s));
            sb.append(s);
        }
        return sb.toString();
    }

    // Decodes bytes string to integer
    public int stringToInt(String bytesStr) {
        int result = 0;
        for(char b : bytesStr.toCharArray())
            result = (result << 8) + (int)b;
        return result;
    }

    // Decodes a single string to a list of strings.
    public List<String> decode(String s) {
        int i = 0, n = s.length();
        List<String> output = new ArrayList();
        while (i < n) {
            int length = stringToInt(s.substring(i, i + 4));
            i += 4;
            output.add(s.substring(i, i + length));
            i += length;
        }
        return output;
    }
}

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

Search

    Table of Contents