LeetCode 820. 单词的压缩编码 (Java版; Meidum)

心已赠人 2023-07-18 14:15 28阅读 0赞

### [welcome to my blog][] ###

## LeetCode 820. 单词的压缩编码 (Java版; Meidum) ##

#### 题目描述 ####

给定一个单词列表，我们将这个列表编码成一个索引字符串 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
    每个单词都是小写字母 。

#### 第一次做; 核心: 1)前缀树; 使用哈希表记录邻居, 方便知道当前节点是否有邻居, 通过isEmpty()判断; 使用数组记录邻居就不方便判断是否有邻居了 ####

class Solution { 
        public int minimumLengthEncoding(String[] words) { 
            HashSet<String> set = new HashSet<>(Arrays.asList(words));
            Trie trie = new Trie();
            for(String s : set){ 
                trie.add(s);
            }
            return trie.getDepthSum();
        }
        class Trie{ 
            Node root;
            HashSet<Node> set;
            Trie(){ 
                root = new Node();
                //装叶子节点; 但是有些叶子节点可能之后就不是叶子节点了, 要小心
                set = new HashSet<>();
            }
    
            void add(String str){ 
                Node cur = root;
                for(int i=str.length()-1; i>=0; i--){ 
                    char ch = str.charAt(i);
                    // int index = ch - 'a';
                    if(!cur.next.containsKey(ch)){ 
                        cur.next.put(ch, new Node());
                    }
                    cur = cur.next.get(ch);
                }
                cur.depth = str.length()+1;//算上#占用的一个深度
                set.add(cur);
            }
    
            int getDepthSum(){ 
                int res = 0;
                for(Node node : set){ 
                    if(node.next.isEmpty()){ 
                        res += node.depth;
                    }
                }
                return res;
            }
        }
    
        class Node{ 
            // Node[] nexts;
            HashMap<Character, Node> next;
            int depth;
            Node(){ 
                // nexts = new Node[26];
                next = new HashMap<>(); //用哈希表的好处是方便直到当前字符有没有下一个字符, 根据isEmpty()判断, 用数组的话就不行了
            }
        }
    }

#### 第一次做; 核心: 1)使用set记录每个单词, 然后针对每一个单词, 考虑其子串\[i,n-1\], 将该子串从set中删除, i>=1, 因为这些子串都是当前单词的后缀 2) HashSet可以使用forEach, HashMap不行 3)Arrays.asList(T… a), 返回值类型是List 3)将所有单词放入set, 可以先过滤掉重复出现的单词 ####

class Solution { 
        public int minimumLengthEncoding(String[] words) { 
            Set<String> set = new HashSet(Arrays.asList(words));
            for(String word : words){ 
                for(int i=1; i<word.length(); i++){ 
                    set.remove(word.substring(i));
                }
            }
            int res=0;
            for(String s : set){ 
                res += s.length()+1;
            }
            return res;
        }
    }

#### [LeetCode优秀题解][LeetCode] JDK8新特性, stream() ####

public int minimumLengthEncoding(String[] words) { 
            Node trie = new Node();
            Set<Node> nodes = new HashSet<>();
            for (String w : words) { 
                Node node = trie;
                for (int i = w.length() - 1; i >= 0; i--)
                    node = node.add(w.charAt(i));
                node.depth = w.length() + 1;
                nodes.add(node);
            }
            return nodes.stream().filter(n -> n.leaf).mapToInt(n -> n.depth).sum();
        }
    
        class Node { 
            final Node[] next = new Node[26];
            boolean leaf = true;
            int depth;
    
            Node add(char c) { 
                if (next[c - 'a'] == null)
                    next[c - 'a'] = new Node();
                leaf = false;
                return next[c - 'a'];
            }
        }

class Solution { 
        public int minimumLengthEncoding(String[] words) { 
            TrieNode root = new TrieNode();
            List<TrieNode> leaves = new  ArrayList<TrieNode>();
            for (String w : new HashSet<>(Arrays.asList(words))) { 
                TrieNode cur = root;
                for (int i = w.length() - 1; i >= 0; --i) { 
                    char j = w.charAt(i);
                    if (!cur.next.containsKey(j)) cur.next.put(j, new TrieNode());
                    cur = cur.next.get(j);
                }
                cur.depth = w.length() + 1;
                leaves.add(cur);
            }
            int res = 0;
            for (TrieNode leaf : leaves) if (leaf.next.isEmpty()) res += leaf.depth;
            return res;
        }
    }
    
    class TrieNode { 
        HashMap<Character, TrieNode> next = new HashMap<>();
        int depth;
    }

[welcome to my blog]: https://littlehaes.com
[LeetCode]: https://leetcode.com/problems/short-encoding-of-words/discuss/125784/Trie-Solution