# 序列化与压缩

* **Bencode 格式 “长度 + 分隔符 + 字符串”， 和 OS 里的 metadata header 是一个思路，在最开始告诉你 data 地址 / 长度 / offset**
* [**Escape** ](https://en.wikipedia.org/wiki/Escape_character)**符的定义是："An escape character is a character which invokes an alternative interpretation on subsequent characters in a character sequence."**

## [Encode and Decode Strings](https://leetcode.com/problems/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](http://stackoverflow.com/questions/853475/whats-the-simplest-way-to-encoding-liststring-into-plain-string-and-decode-it) 上有个帖子讲的不错，思路和我原来的代码也很接近。

```java
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](https://en.wikipedia.org/wiki/Bencode), 简单讲就是 “长度 + 分隔符 + 字符串” 的 encoding.

于是有了这段参考 LeetCode 论坛之后的代码。 其实空间时间上不算特别经济，但是胜在简洁。原 string 中间如果有 delimiter 也不要紧，因为可以根据 length 直接跳过，再寻找 delimiter 的时候一定是有效字符。

* **思想上讲和 OS 的 file system 是非常像的，在实际 data 最前面的 header 里会存 metadata，告诉你下一段数据的内存地址或者offset。**

```java
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**](https://en.wikipedia.org/wiki/Escape_character) **符的正确定义是：看到了就跳过，但是 escape 符后面的一定是有效字符。**
* **于是一个落单的 '#' 代表单词 delimiter ;**
* **原字符串的 '#' 变成了 '/ + #'；这样保证可以加进去但是又不会作为 '#' 单独被判断；**
* **原字符串的 '/' 就变成了 '//'，实际意义是 "escape 符 + 有效字符"。**

```java
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](https://leetcode.com/problems/unique-word-abbreviation/)

这题本身非常简单，但是写 sample test case 的人有点智障。。。得看着挂了的 test case 一点一点猜才能知道这题到底是想干啥。

这题的意思是，我们要看的是一个 key 到底是否有效； 给你一个 word，如果字典里面完全没有一样的 abbreviation -> true; 如果有一样的 abbreviation 但是全和你的 word 是一样的单词，也返回 true；其他的都是 false;

```java
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](https://leetcode.com/problems/generalized-abbreviation/)

典型的搜索问题，对于 "word" ，该词的搜索图和状态空间如图所示：

![](/files/-MUt7arbIJVdnR5AuqPR)

第一遍 AC 的代码\~

* **错误1：不能盲目用 indexOf(len) 去找下一个起点，因为 len 作为一个数字是可以重复的。**
* **错误2：用 lastIndexOf 也不行，因为数字不都是一位数，有肯能会出现重复数字的两位数。**
* **因此， 最稳的做法是，pos 一定新 string 的起点，然后加上数字 string 的长度，再加一。**

```java
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，简单强大，非常值得总结一个\~

```java
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) [字符串嵌套压缩 / 解压缩 ](http://www.1point3acres.com/bbs/forum.php?mod=viewthread\&tid=191823\&highlight=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]好。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mnunknown.gitbook.io/algorithm-notes/stringff0c_zi_fu_chuan_lei/526_string.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.