序列化与压缩
Bencode 格式 “长度 + 分隔符 + 字符串”, 和 OS 里的 metadata header 是一个思路,在最开始告诉你 data 地址 / 长度 / offset
Escape 符的定义是:"An escape character is a character which invokes an alternative interpretation on subsequent characters in a character sequence."
这题挺好玩的,既实用又有意思,做了一番调查之后有两种方法都可以写。
这题考察的就是在 serialization 中如何解决各种歧义,还有 corner case 是否考虑的足够周全。
当发现题目本身重点考察 corner case 的时候,一定记得先列出需要解决的问题,把各种 corner case 先列出来再动手。
输入字符在 256 个 ASC II 码的集合中,所用的 encode 字符也是同一个集合。所以不能引入新的特殊符号去解决问题。
用什么字符做分隔符,表示 string 的间隔?
如果原字符中有分隔符,如何区分?
如何正确的 encode 空字符串,还有多个空字符串?
举个例子,我如果用 '#' 代表字符分隔符,'#' 代表原字符串中的 '#' 的话,几个必须要考虑的 test case 是:
["\"]
["#"]
["\#"]
[""]
["", ""]
先说一下我几次不成功的尝试。。下面的代码不能 AC,只能过 305 / 316 个 test case.
基本 encode 思路是让每个 encoded string 不以 '#' 结尾,落单的 '#' 代表空字符串。
然后 decode 时依次读取,看到字符先加进去,如果发现后面的是 '#' 而前一个是 '\' 的话,抹掉一位。
不过依然解决的不完美,因为下面这个 test case 里
Input: ["" ""]
Output: [""]
Expected: ["",""]
中间的过渡 string 是 "#"。
这个问题在 StackOverflow 上有个帖子讲的不错,思路和我原来的代码也很接近。
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){
for(int i = 0; i < str.length(); i++){
if(str.charAt(i) == '#'){
sb.append('\\');
}
sb.append(str.charAt(i));
}
sb.append('#');
}
if(sb.length() > 1) sb.setLength(sb.length() - 1);
return sb.toString();
}
// Decodes a single string to a list of strings.
public List<String> decode(String s) {
List<String> list = new ArrayList<String>();
StringBuilder sb = new StringBuilder();
for(int i = 0; i < s.length(); i++){
if(s.charAt(i) != '#'){
sb.append(s.charAt(i));
} else {
// Found '\#' , remove '\' and add '#'
if(i - 1 >= 0 && s.charAt(i - 1) == '\\'){
sb.setLength(sb.length() - 1);
sb.append('#');
} else {
list.add(sb.toString());
sb.setLength(0);
}
}
}
if(sb.length() > 0){
list.add(sb.toString());
}
return list;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(strs));
BitTorrent 有一个P2P跨平台的序列化规范,简单易懂,叫 Bencode, 简单讲就是 “长度 + 分隔符 + 字符串” 的 encoding.
于是有了这段参考 LeetCode 论坛之后的代码。 其实空间时间上不算特别经济,但是胜在简洁。原 string 中间如果有 delimiter 也不要紧,因为可以根据 length 直接跳过,再寻找 delimiter 的时候一定是有效字符。
思想上讲和 OS 的 file system 是非常像的,在实际 data 最前面的 header 里会存 metadata,告诉你下一段数据的内存地址或者offset。
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> list = new ArrayList<String>();
int i = 0;
while(i < s.length()){
int delimiter = s.indexOf(':', i);
int size = Integer.valueOf(s.substring(i, delimiter));
list.add(s.substring(delimiter + 1, delimiter + 1 + size));
i = delimiter + 1 + size;
}
return list;
}
}
继续参考了一下论坛的各种解法之后,不利用length信息这题也可以做,只是需要对“escape符”有更好的理解才行。
Escape 符的正确定义是:看到了就跳过,但是 escape 符后面的一定是有效字符。
于是一个落单的 '#' 代表单词 delimiter ;
原字符串的 '#' 变成了 '/ + #';这样保证可以加进去但是又不会作为 '#' 单独被判断;
原字符串的 '/' 就变成了 '//',实际意义是 "escape 符 + 有效字符"。
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){
for(int i = 0; i < str.length(); i++){
char chr = str.charAt(i);
if(chr == '/'){
sb.append("//");
} else if(chr == '#'){
sb.append("/#");
} else {
sb.append(chr);
}
}
sb.append("#");
}
return sb.toString();
}
// Decodes a single string to a list of strings.
public List<String> decode(String s) {
List<String> res = new ArrayList<>();
StringBuilder str = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '/') {
str.append(s.charAt(++i));
} else if (s.charAt(i) == '#') {
res.add(str.toString());
str.setLength(0);
} else {
str.append(s.charAt(i));
}
}
return res;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(strs));
这题本身非常简单,但是写 sample test case 的人有点智障。。。得看着挂了的 test case 一点一点猜才能知道这题到底是想干啥。
这题的意思是,我们要看的是一个 key 到底是否有效; 给你一个 word,如果字典里面完全没有一样的 abbreviation -> true; 如果有一样的 abbreviation 但是全和你的 word 是一样的单词,也返回 true;其他的都是 false;
public class ValidWordAbbr {
HashMap<String, String> map;
public ValidWordAbbr(String[] dictionary) {
map = new HashMap<String, String>();
for(String str:dictionary){
String key = getKey(str);
// If there is more than one string belong to the same key
// then the key will be invalid, we set the value to ""
if(map.containsKey(key)){
if(!map.get(key).equals(str)){
map.put(key, "");
}
} else {
map.put(key, str);
}
}
}
public boolean isUnique(String word) {
return !map.containsKey(getKey(word))||map.get(getKey(word)).equals(word);
}
String getKey(String str){
if(str.length() <= 2) return str;
return str.charAt(0)+Integer.toString(str.length()-2)+str.charAt(str.length()-1);
}
}
典型的搜索问题,对于 "word" ,该词的搜索图和状态空间如图所示:

第一遍 AC 的代码~
错误1:不能盲目用 indexOf(len) 去找下一个起点,因为 len 作为一个数字是可以重复的。
错误2:用 lastIndexOf 也不行,因为数字不都是一位数,有肯能会出现重复数字的两位数。
因此, 最稳的做法是,pos 一定新 string 的起点,然后加上数字 string 的长度,再加一。
public class Solution {
public List<String> generateAbbreviations(String word) {
List<String> list = new ArrayList<String>();
list.add(word);
dfs(list, word, 0);
return list;
}
private void dfs(List<String> list, String word, int startIndex){
if(startIndex >= word.length()) return;
// Iterate through all lengths
for(int len = 1; len <= word.length() - startIndex; len++){
for(int pos = startIndex; pos <= word.length() - len; pos++){
String nextWord = word.substring(0, pos) + len + word.substring(pos + len);
String number = "" + len;
list.add(nextWord);
dfs(list, nextWord, pos + number.length() + 1);
}
}
}
}
参考了论坛之后,觉得这个做法也特别巧妙,图像化的话,和我刚才画的搜索图不一样,而是从原始 String 出发,对于每个位置进行检查;每个位置都有 "加字母" 或者 "不加,并入数字" 两种选择,和 remove parentheses 与 add operators 的思路非常的像,时间复杂度也一目了然,O(2^n).
这种在 String 上,相对于每个字符考虑多种可能的 DFS + backtracking,简单强大,非常值得总结一个~
public class Solution {
public List<String> generateAbbreviations(String word) {
List<String> list = new ArrayList<>();
dfs(list, new StringBuilder(), word.toCharArray(), 0, 0);
return list;
}
private void dfs(List<String> list, StringBuilder sb, char[] word, int index, int curNum){
int len = sb.length();
if(index == word.length){
if(curNum != 0) sb.append(curNum);
list.add(sb.toString());
} else {
// Don't add, merge to current number
dfs(list, sb, word, index + 1, curNum + 1);
// Add current char
if(curNum != 0) sb.append(curNum);
dfs(list, sb.append(word[index]), word, index + 1, 0);
}
sb.setLength(len);
}
}
(Google) 字符串嵌套压缩 / 解压缩
变种1:
http://www.1point3acres.com/bbs/thread-189365-1-1.html
上来大概问了5分钟background然后直接上题,一个string decompression的题。。不知道是不是原题反正没见过。。题目如下.
2[abc]3[a]c => abcabcabcaaac; 2[ab3[d]]2[cc] => abdddabdddcc 输入 输出 一开始用了一个栈,写着写着嵌套的逻辑卡住了,最后用俩stack解决。。然后follow-up问的是不要输出string而是输出解压后的K-th character,主要也还是嵌套情况就从内到外把疙瘩解开以后再算。。然后我问俩问题就结束了。整体感觉妹子面试官人很nice 反应很快而且不是特别picky的那种。
变种2:
“3a2[mtv]ac”, decompress to: aaamtvmtvac,括号可以嵌套。 这个我觉得不是很难,大概花了15分钟理清了思路并写好了代码,大概就是找匹配括号递归解,面试官也找不到bug表示认同。
但吊诡的地方来了,面试官说把这种字符串compress回去...这显然有多种情况,于是我问是不是要求压缩后最短,面试官说肯定越短越好。 比如对于aaaa, 肯定4a比2[aa]好。
Last updated
Was this helpful?