序列化与压缩

  • 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."

Encode and Decode Strings

这题挺好玩的，既实用又有意思，做了一番调查之后有两种方法都可以写。

  • 这题考察的就是在 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));

Unique Word Abbreviation

这题本身非常简单，但是写 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);
    }
}

Generalized Abbreviation

典型的搜索问题，对于 "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]好。

PreviousString / LinkedList 大数运算Next5/24 String 杂题

Last updated