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

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

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）排序 & 哈希集合
思路参考本题官方题解。

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

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

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

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

有关前缀树的具体细节，可以参考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;
    }
}