LeetCode_前缀树_排序_哈希集合_中等_720.词典中最长的单词

Love The Way You Lie 2024-04-07 13:21 132阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给出一个字符串数组 words 组成的一本英语词典。返回 words 中最长的一个单词，该单词是由 words 词典中其他单词逐步添加一个字母组成。若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。

**示例 1：**  
输入：words = \[“w”,“wo”,“wor”,“worl”, “world”\]  
输出：“world”  
解释： 单词"world"可由"w", “wo”, “wor”, 和 "worl"逐步添加一个字母组成。

**示例 2：**  
输入：words = \[“a”, “banana”, “app”, “appl”, “ap”, “apply”, “apple”\]  
输出：“apple”  
解释：“apply” 和 “apple” 都能由词典中的单词组成。但是 “apple” 的字典序小于 “apply”

**提示：**  
1 <= words.length <= 1000  
1 <= words\[i\].length <= 30  
所有输入的字符串 words\[i\] 都只包含小写字母。

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/longest-word-in-dictionary

## 2.思路 ##

（1）排序 & 哈希集合  
思路参考[本题官方题解][Link 1]。

① 先对数组 words 进行排序，排序规则如下：  
1）首先按照单词长度进行升序排序；  
2）如果单词长度相同，则按照字典序降序排序；

② 定义哈希集合 hashSet，并将空串 (“”) 加入其中，然后再开始遍历数组 words，假设 words\[i\] = “worl”，判断当前单词去掉最后一个字母的前缀（即"wor"）是否存在于 hashSet 中：  
1）如果存在，则说明 hashSet 一定还包含 “w”、“wo”，此时的 “worl” 有可能是最终答案，用 res 保存起来。  
2）如果不存在，则说明该单词一定不满足题目要求，不予考虑即可。

③ 这里需要注意的是，由于在之前的排序过程中，如果单词长度相同，则按照字典序降序排序，这样就保证了**如果同时存在多个答案，在遍历数组 words 的过程中，字典序最小的答案在靠后的位置，所以 res 保存的就是多个可行答案中字典序最小的单词！**

（2）前缀树  
思路参考[本题官方题解][Link 1]。

有关前缀树的具体细节，可以参考[208. 实现 Trie (前缀树)][208. _ Trie]这篇文章。

## 3.代码实现（Java） ##

//思路1————排序 & 哈希集合
    class Solution {
        
        public String longestWord(String[] words) {
        
            String res = "";
            int length = words.length;
            /*
                将数组 words 进行排序，排序规则如下：
                (1) 首先按照单词长度进行升序排序；
                (2) 如果单词长度相同，则按照字典序降序排序
            */
            Arrays.sort(words, (word1, word2) -> {
        
                //返回值为正数，则交换 word1 和 word2
               if (word1.length() != word2.length()) {
        
                   return word1.length() - word2.length();
               } else {
        
                   return word2.compareTo(word1);
               }
            });
            Set<String> hashSet = new HashSet<>();
            candidates.add("");
            for (int i = 0; i < length; i++) {
        
                String word = words[i];
                /*
                	假设 words[i] = "worl"
    				判断当前单词去掉最后一个字母的前缀(即"wor")是否存在于 hashSet 中
    				(1) 如果存在，则说明 hashSet 一定还包含 "w"、"wo"，此时的 "worl" 有可能是最终答案，用 res 保存起来。
    				(2) 如果不存在，则说明该单词一定不满足题目要求，不予考虑即可。
    			*/
                if (hashSet.contains(word.substring(0, word.length() - 1))) {
        
                    hashSet.add(word);
                    //更新 res
                    res = word;
                }
            }
            return res;
        }
    }

//思路2————前缀树
    class Solution {
        
        public String longestWord(String[] words) {
        
            String res = "";
            Trie trie = new Trie();
            //将数组 words 中的所有单词插入到前缀树中
            for (String word : words) {
        
                trie.insert(word);
            }
            for (String word : words) {
        
                if (trie.search(word)) {
        
                	/*
    					更新 res 的条件：
    					(1) 当前 word 的长度大于 res 的长度；
    					(2) 或者当前 word 的长度等于 res 的长度，但是 word 的字典序小于 res。
    				*/
                    if (word.length() > res.length() || (word.length() == res.length() && word.compareTo(res) < 0)) {
        
                        //更新 res
                        res = word;
                    }
                }
            }
            return res;
        }
    }
    
    class Trie {
        
        private Trie[] children;
        private boolean isEnd;
        
        public Trie() {
        
            //每个节点最多有 26 个子节点，分别对应 26 个小写英文字母
            children = new Trie[26];
            isEnd = false;
        }
        
        //插入字符串
        public void insert(String word) {
        
            Trie node = this;
            for (int i = 0; i < word.length(); i++) {
        
                char ch = word.charAt(i);
                int index = ch - 'a';
                if (node.children[index] == null) {
        
                    node.children[index] = new Trie();
                }
                node = node.children[index];
            }
            node.isEnd = true;
        }
        
        public boolean search(String word) {
        
            Trie node = this;
            for (int i = 0; i < word.length(); i++) {
        
                char ch = word.charAt(i);
                int index = ch - 'a';
                if (node.children[index] == null || !node.children[index].isEnd) {
        
                    return false;
                }
                node = node.children[index];
            }
            return node != null && node.isEnd;
        }
    }

[Link 1]: https://leetcode.cn/problems/longest-word-in-dictionary/solution/ci-dian-zhong-zui-chang-de-dan-ci-by-lee-k5gj/
[208. _ Trie]: https://blog.csdn.net/weixin_43004044/article/details/125231290