271. Encode and Decode Strings

可想而知,又是一道corner case多到自杀的题。

这题考察的就是在 serialization 中如何解决各种歧义,还有 corner case 是否考虑的足够周全。

当发现题目本身重点考察 corner case 的时候,一定记得先列出需要解决的问题,把各种 corner case 先列出来再动手。

输入字符在 256 个 ASC II 码的集合中,所用的 encode 字符也是同一个集合。所以不能引入新的特殊符号去解决问题。

  • 用什么字符做分隔符,表示 string 的间隔?
  • 如果原字符中有分隔符,如何区分?
  • 如何正确的 encode 空字符串,还有多个空字符串?

我的失败尝试就不啰嗦了,直接说比较好的思路。

BitTorrent有一个P2P跨平台的序列化规范,P2P来头太大了,没有P2P,就没有比特币没有盗版市场,这个扯远了。

要说的序列化规范是Bencode, 简单讲就是 “长度 + 分隔符 + 字符串” 的 encoding

其实空间时间上不算特别经济,但是胜在简洁。原 string 中间如果有 delimiter 也不要紧,因为可以根据 length 直接跳过,再寻找 delimiter 的时候一定是有效字符。

思想上讲和 OS 的 file system 是非常像的,在实际 data 最前面的 header 里会存 metadata,告诉你下一段数据的内存地址或者offset。从这一点来讲,也让人想起TCP header中的offset。

注意indexOf(':', i)这个函数,从index为i处开始寻找第一个':',valueOf也是,都是string处理常用的函数。

public class Codec {

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

    // Decodes a single string to a list of strings.
    public List<String> decode(String s) {
        List<String> result = new ArrayList<>();

        int i = 0;
        while (i < s.length()) {
            int delimiter = s.indexOf(':', i);
            int size = Integer.valueOf(s.substring(i, delimiter));
            result.add(s.substring(delimiter + 1, delimiter + 1 + size));
            i = delimiter + 1 + size;
        }
        return result;
    }
}

results matching ""

    No results matching ""