820. 单词的压缩编码

一时失言乱红尘 2022-12-07 15:30 100阅读 0赞

# 题目： #

[820. 单词的压缩编码][820.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]

# 题解： #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 2]

## 1. 题解一：存储后缀 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 4]  
![在这里插入图片描述][20200916203540802.png_pic_center]

## 2. 题解二：字典树 ##

1.  解释一：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 5]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 6]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 7]
2.  解释二：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 8]

# 代码： #

## 1. 代码一：存储后缀 ##

// 方法一: 存储后缀
    public static int minimumLengthEncoding(String[] words) { 
        Set<String> set = new HashSet<>(Arrays.asList(words));
        for(String word: words)
        { 
            for(int k = 1; k < word.length(); k++)
            { 
                set.remove(word.substring(k));
            }
        }
        int ans = 0;
        for(String word: set)
        { 
            ans += word.length() + 1;
        }
        return ans;
    }

## 2. 代码二：字典树 ##

import java.util.*;
    
    public class code820 { 
    
        // 方法二: 字典树
        public static int minimumLengthEncoding(String[] words) { 
            int len = 0;
            Trie trie = new Trie();
            // 先对单词列表根据单词长度由长到短排序
            Arrays.sort(words, (s1, s2) -> s2.length() - s1.length());
            // 单词插入trie，返回该单词增加的编码长度
            for(String word: words)
            { 
                len += trie.insert(word);
            }
            return len;
        }
    
        public static void main(String[] args) { 
            String words[] = { "time", "me", "bell"};
            int res = minimumLengthEncoding(words);
            System.out.println(res);
        }
    }
    
    // 定义tire
    class Trie
    { 
        TrieNode root; // trie的根节点定义成一个空节点
    
        public Trie()
        { 
            root = new TrieNode();
        }
    
        public int insert(String word)
        { 
            TrieNode cur = root;
            boolean isNew = false;
            // 倒着插入单词
            for(int i = word.length() - 1; i >= 0; i--)
            { 
                int c = word.charAt(i) - 'a';
                if(cur.children[c] == null)
                { 
                    isNew = true; // 是新单词
                    cur.children[c] = new TrieNode();
                }
                cur = cur.children[c];
            }
            // 如果是新单词的话，编码长度增加新单词的长度+1，否则不变。
            return isNew ? word.length() + 1 : 0;
        }
    }
    
    // trie的节点的定义
    class TrieNode
    { 
        char val;
        TrieNode[] children = new TrieNode[26];
    
        public TrieNode()
        { 
    
        }
    
        public TrieNode(char val)
        { 
            this.val = val;
        }
    }

# 参考： #

1.  [单词的压缩编码][Link 1]
2.  [99% Trie 吐血攻略，包教包会][99_ Trie]
3.  [无需字典树，轻轻一反转，结果就出来（C++/Java/Python）][C_Java_Python]
4.  [手撕字典树(Trie 树) C++ 另附暴力哈希解法][Trie _ C_]

[820.]: https://leetcode-cn.com/problems/short-encoding-of-words/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/7c49296e0259433fac203363be5e41b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/7e00b2b31e3b40a391b5b9de4c525ceb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/c98b38aa694245f781dd691e074892d7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/d84d2fb8382f42bf9075f72edeaaf618.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/617ec40a159b41d399eb8e2f9cd0f32e.png
[20200916203540802.png_pic_center]: /images/20221123/627dda70c3a44d4fa6f401c1884c0a52.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/78618085922d4d508c2db6214ff533bb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/c56eb88f4b454764b9e87aad1a72d0c1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221123/9a4db2e2208142dc968b786819307b49.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221123/2d82b697a355448a8bf4d5c54d67f0c3.png
[Link 1]: https://leetcode-cn.com/problems/short-encoding-of-words/solution/dan-ci-de-ya-suo-bian-ma-by-leetcode-solution/
[99_ Trie]: https://leetcode-cn.com/problems/short-encoding-of-words/solution/99-java-trie-tu-xie-gong-lue-bao-jiao-bao-hui-by-s/
[C_Java_Python]: https://leetcode-cn.com/problems/short-encoding-of-words/solution/wu-xu-zi-dian-shu-qing-qing-yi-fan-zhuan-jie-guo-j/
[Trie _ C_]: https://leetcode-cn.com/problems/short-encoding-of-words/solution/shou-si-zi-dian-shu-trie-shu-c-by-time-limit/