Skip to main content

🟡 剑指 Offer II 065. 最短的单词编码

LeetCode 提示

题目难度 中等

原题链接 🔗 leetcode

这道题可以直接用消灭后缀的方法来做，另外注意到每个单词最长7位，所以直接枚举消除每个单词的7个后缀也是可以的。

不过这里看到有一个更为先进的方法，字典树desu。

题解1#

官方题解在这里。

抄袭过程中有两个注意点：

  1. endNodes 是 HashMap，而不是TrieNode[]：如果有重复的相同单词，HashMap可以顺便解决去重的问题，但array不行，从而导致多个相同单词重复计算长度。
  2. res 到底是怎么计算的？还是从endNodes入手：
    1. 怎么判断endNodes里哪些node是可用的？node.cnt == 0说明这个节点是叶子，可以用
    2. 然后要怎么用？endNodes的value值表示插入这个node的单词index，找到对应的单词直接累加其长度即可
class TrieNode {    int cnt;    TrieNode[] children;
    public TrieNode() {        this.cnt = 0;        this.children = new TrieNode[26];    }
    public TrieNode get(char c) {        if (this.children[c-'a'] == null) {            this.children[c-'a'] = new TrieNode();            this.cnt += 1;        }        return this.children[c-'a'];    }}
class Solution {    public int minimumLengthEncoding(String[] words) {        int n = words.length;        HashMap<TrieNode, Integer> endNodes = new HashMap<>();        TrieNode root = new TrieNode();
        for (int wi=0; wi<n; wi+=1) {            TrieNode cur = root;            String word = words[wi];            for (int i=word.length()-1; i>=0; i-=1) {                cur = cur.get(word.charAt(i));            }            endNodes.put(cur, wi);        }                int res = 0;        for (TrieNode node: endNodes.keySet()) {            if (node.cnt == 0) {                res += words[endNodes.get(node)].length() + 1;            }        }
        return res;    }}