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;
}
}