单词的压缩编码

作者: MrHitchcock | 来源:发表于2020-03-28 14:44 被阅读0次

单词的压缩编码
单词的压缩编码
单词的压缩编码
单词的压缩编码-13.字典树
《算法》笔记 17 - 数据压缩
Leetcode 单词的压缩编码
820-单词的压缩编码
820. 单词的压缩编码
『字典树』单词的压缩编码820
2018-03-28 Huffman树

附上一道shell编程，关于识别有效电话号码。解题思路很简单，使用正则即可。

题目描述：给定一个包含电话号码列表（一行一个电话号码）的文本文件 file.txt，写一个 bash 脚本输出所有有效的电话号码。

你可以假设一个有效的电话号码必须满足以下两种格式： (xxx) xxx-xxxx 或 xxx-xxx-xxxx。（x 表示一个数字）

你也可以假设每行前后没有多余的空格字符。

示例:
假设 file.txt 内容如下：
987-123-4567
123 456 7890
(123) 456-7890
你的脚本应当输出下列有效的电话号码：
987-123-4567
(123) 456-7890
链接：https://leetcode-cn.com/problems/valid-phone-numbers

题解：

正则示意图

最终表达式如下：
^([0-9]{3}-|([0-9]{3}) )[0-9]{3}-[0-9]{4}$
shell命令：
grep与awk
grep
grep -P '^([0-9]{3}-|([0-9]{3}) )[0-9]{3}-[0-9]{4} $' file.txt awk/gawk awk '/^([0-9]{3}-|$[0-9]{3}$ )[0-9]{3}-[0-9]{4}$ /' file.txt
或者
gawk '/^([0-9]{3}-|([0-9]{3}) )[0-9]{3}-[0-9]{4}$/' file.txt
附加快速查看表
为了方便查看，列出对应的特殊字符表以及表达方式
特殊字符表达
特殊字符转义表达特殊含义
() () 标记一个子表达式的开始和结束位置。子表达式可以获取供以后使用
$\$ 匹配输入字符串的结尾位置

* 匹配前面的子表达式零次或多次

+ 匹配前面的子表达式一次或多次
. . 匹配除换行符 \n 之外的任何单字符
[ ] [] 标记一个中括号表达式的开始。要匹配 [，请使用 [。
? ? 匹配前面的子表达式零次或一次，或指明一个非贪婪限定符
\ \ 将下一个字符标记为或特殊字符、或原义字符、或向后引用、或八进制转义符
^ ^ 匹配输入字符串的开始位置，除非在方括号表达式中使用，当该符号在方括号表达式中使用时，表示不接受该方括号表达式中的字符集合
{} {} 标记限定符表达式的开始
| | 指明两项之间的一个选择
Note 表含义中的出现次数：限定符前面字符的出现次数。

限定符表达含义

出现次数>=0

出现次数>=1
? 出现次数 0 or 1, 等价{0,1}
{n} 出现次数=n
{n,} 出现次数>=n
{n, m} n=< 出现次数<= m

定位符表达含义
^ 字符串开始的位置
$ 字符串结束的位置
\b 限定单词(字)的字符，常用来确定一个单词，可以结合两个‘\b’使用
\B 限定非单词(字)边界的字符，用的很少
链接：https://leetcode-cn.com/problems/valid-phone-numbers/solution/zheng-ze-biao-da-shi-zhong-xian-ding-fu-yu-ding-we/

今日份的算法题如下：

题目描述：给定一个单词列表，我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。

例如，如果这个列表是 ["time", "me", "bell"]，我们就可以将其表示为 S = "time#bell#" 和 indexes = [0, 2, 5]。

对于每一个索引，我们可以通过从字符串 S 中索引的位置开始读取字符串，直到 "#" 结束，来恢复我们之前的单词列表。

那么成功对给定单词列表进行编码的最小字符串长度是多少呢？

示例：
输入: words = ["time", "me", "bell"]
输出: 10
说明: S = "time#bell#" ， indexes = [0, 2, 5] 。

提示：
1 <= words.length <= 2000
1 <= words[i].length <= 7
每个单词都是小写字母。
链接：https://leetcode-cn.com/problems/short-encoding-of-words

解题思路1：

题目要求输入一组字符串列表，输出最小编码后的字符串长度；
如列表中有重复字符串，需合并；
如列表中存在一个字符串是另一个的后缀，需合并；
由于题目对列表和字符串长度均有限制，则可以采用遍历的粗暴方法。

Python版：

class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        good = set(words)
        for word in words:
            for k in range(1, len(word)):
                good.discard(word[k:])

        return sum(len(word) + 1 for word in good)

Tips：

使用python的集合可以方便地去重
分别遍历字符串和字符串中的每个字符，用切片的方式比较
set.discard删除不存在的不会报错，而remove删除不存在会报错的
由于set(words) = k为0时的情况，所以最后k从1开始遍历即可
最后sum函数中对每个字符串都加1表示‘#’的长度
C++版：

class Solution {
public:
    int minimumLengthEncoding(vector<string>& words) {
        unordered_set<string> good(words.begin(), words.end());
        for (const string& word: words) {
            for (int k = 1; k < word.size(); ++k) {
                good.erase(word.substr(k));
            }
        }

        int ans = 0;
        for (const string& word: good) {
            ans += word.size() + 1;
        }
        return ans;
    }
};

Tips:

C++的vector（向量）容器是封装了动态大小数组的顺序容器，能存放任意类型的动态数组
C++中指定字符串长度的方法为word.size()，Java是word.length()，python是len(word)
使用unordered_set（C++11中的新特性），基于哈希表。C++ 11中对unordered_set描述大体如下：无序集合容器（unordered_set）是一个存储唯一(unique，即无重复）的关联容器（Associative container），容器中的元素无特别的秩序关系，该容器允许基于值的快速元素检索，同时也支持正向迭代。在一个unordered_set内部，元素不会按任何顺序排序，而是通过元素值的hash值将元素分组放置到各个槽(Bucker，也可以译为“桶”），这样就能通过元素值快速访问各个对应的元素（均摊耗时为O（1））。
原型中的Key代表要存储的类型，而hash<Key>也就是你的hash函数，equal_to<Key>用来判断两个元素是否相等，allocator<Key>是内存的分配策略。一般情况下，我们只关心hash<Key>和equal_to<Key>参数，下面将介绍这两部分。（参考原文链接：https://blog.csdn.net/vevenlcf/article/details/51743058）
C++直接提供了substr函数，需要两个参数，即字符串的begin和end，可以很快地识别出字符串后缀；
erase是容器中定义的擦除函数：
std::vector::erase()
　函数原型：iterator erase (iterator position);　　//删除指定元素
iterator erase (iterator first, iterator last);　　//删除指定范围内的元素
返回值：指向删除元素(或范围)的下一个元素。
Java版：

class Solution {
    public int minimumLengthEncoding(String[] words) {
        Set<String> good = new HashSet(Arrays.asList(words));
        for (String word: words) {
            for (int k = 1; k < word.length(); ++k)
                good.remove(word.substring(k));
        }

        int ans = 0;
        for (String word: good)
            ans += word.length() + 1;
        return ans;
    }
}

Tips:

使用了Array.asList()方法，目的是将一个变长参数或数组转换为List
使用HashSet()方法，构造一个新的空set，remove()是HashSet的常用方法；C++中的substr()方法在Java中变为substring()

解题思路2：利用Trie树。反序将字符元素插入Trie树中，保留根节点为空，最后统计叶子节点数+1即为答案。

Trie树构造
Python版

class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        words = list(set(words)) #remove duplicates
        #Trie is a nested dictionary with nodes created
        # when fetched entries are missing
        Trie = lambda: collections.defaultdict(Trie)
        trie = Trie()

        #reduce(..., S, trie) is trie[S[0]][S[1]][S[2]][...][S[S.length - 1]]
        nodes = [reduce(dict.__getitem__, word[::-1], trie)
                 for word in words]

        #Add word to the answer if it's node has no neighbors
        return sum(len(word) + 1
                   for i, word in enumerate(words)
                   if len(nodes[i]) == 0)

Tips：

利用Python写trie树真的很简洁...
在计算node时，用到了特殊方法getitem。凡是在类中定义了这个getitem 方法，那么它的实例对象（假定为p），可以像这样
p[key] 取值，当实例对象做p[key] 运算时，会调用类中的方法getitem。
一般如果想使用索引访问元素时，就可以在类中定义这个方法（getitem(self, key) ）。 参考python魔方方法
reduce()函数。reduce() 函数会对参数序列中元素进行累积。函数将一个数据集合（链表，元组等）中的所有数据进行下列操作：用传给 reduce 中的函数 function（有两个参数）先对集合中的第 1、2 个元素进行操作，得到的结果再与第三个数据用 function 函数运算，最后得到一个结果。
语法
- reduce() 函数语法：reduce(function, iterable[, initializer])
- 参数
  function -- 函数，有两个参数
  iterable -- 可迭代对象
  initializer -- 可选，初始参数
- 例子：reduce(lambda x, y: x+y, [1,2,3,4,5]) # 使用 lambda 匿名函数
  输出：15
先构造了trie字典，key为逆序排列的words列表中的每个字符，调用reduce函数进行累积计算，计算结果若不为0，则是后缀词。
当word = 'time'时，reduce返回结果：

非后缀词
当word = 'me' 时，reduce返回结果：

后缀词
因为pythonic风格对此题过于明显，就不放上C++和Java版本了...