题目描述
这是 LeetCode 上的 720. 词典中最长的单词 ，难度为 简单。
Tag : 「模拟」、「哈希表」、「字典树」
给出一个字符串数组 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 <= 10001<=words.length<=1000
- 1 <= words[i].length <= 301<=words[i].length<=30
- 所有输入的字符串 words[i]words[i] 都只包含小写字母。
模拟
数据范围很小，我们可以直接模拟来做。
先将所有的 words[i]words[i] 存入 Set 集合，方便后续可以近似 O(1)O(1) 查询某个子串是否存在 wordswords 中。
遍历 wordswords 数组（题目没有说 wordswords 不重复，因此最好遍历刚刚预处理的 Set 集合），判断每个 words[i]words[i] 是否为「合法单词」，同时利用当前的最长单词来做剪枝。
不算剪枝效果，该做法计算量不超过 10^6106，可以过。
代码：
class Solution { public String longestWord(String[] words) { String ans = ""; Set<String> set = new HashSet<>(); for (String s : words) set.add(s); for (String s : set) { int n = s.length(), m = ans.length(); if (n < m) continue; if (n == m && s.compareTo(ans) > 0) continue; boolean ok = true; for (int i = 1; i <= n && ok; i++) { String sub = s.substring(0, i); if (!set.contains(sub)) ok = false; } if (ok) ans = s; } return ans; } } 复制代码
- 时间复杂度：预处理
Set集合复杂度近似 O(n)O(n)；判断某个 words[i]words[i] 是否合法需要判断所有子串是否均在 wordswords 中，复杂度为 O(m^2)O(m2)，其中 mm 为字符串长度，处理 words[i]words[i] 的过程还使用到compareTo操作，其复杂度为 O(\min(N, M))O(min(N,M))，其中 NN 和 MM 为参与比较的两字符串长度，该操作相比于生成子串可忽略，而对于一个长度为 mm 的字符串而言，生成其所有的子串的计算量为首项为 11，末项为 mm，公差为 11 的等差数列求和结果。整体复杂度为 O(\sum_{i = 0}^{n - 1}words[i].length^2)O(∑i=0n−1words[i].length2) - 空间复杂度：O(\sum_{i = 0}^{n - 1}words[i].length)O(∑i=0n−1words[i].length)
字典树
上述解法中「枚举某个 words[i]words[i] 的所有子串，并判断子串是否在 wordswords 数组中出现」的操作可使用「字典树」来实现。
不了解「Trie / 字典树」的同学可以看前置 🧀：字典树入门。里面通过图例展示了字典树基本形态，以及提供了「数组实现」和「TrieNode 实现」两种方式，还有「数组大小估算方式」和「Trie 应用面」介绍。
回到本题，起始先将所有的 words[i]words[i] 存入字典树，并记录每个字符的结尾编号。
对于某个 words[i]words[i] 而言，其能成为「合法单词」的充要条件为：
words[i]words[i] 的每个前缀编号都有「以结尾编号」所被记录。
一些细节：为了防止每个样例都
new大数组，我们使用static进行优化，并在跑样例前进行相应的清理工作。
代码：
class Solution { static int N = 30010, M = 26; static int[][] tr = new int[N][M]; static boolean[] isEnd = new boolean[N]; static int idx = 0; void add(String s) { int p = 0, n = s.length(); for (int i = 0; i < n; i++) { int u = s.charAt(i) - 'a'; if (tr[p][u] == 0) tr[p][u] = ++idx; p = tr[p][u]; } isEnd[p] = true; } boolean query(String s) { int p = 0, n = s.length(); for (int i = 0; i < n; i++) { int u = s.charAt(i) - 'a'; p = tr[p][u]; if (!isEnd[p]) return false; } return true; } public String longestWord(String[] words) { Arrays.fill(isEnd, false); for (int i = 0; i <= idx; i++) Arrays.fill(tr[i], 0); idx = 0; String ans = ""; for (String s : words) add(s); for (String s : words) { int n = s.length(), m = ans.length(); if (n < m) continue; if (n == m && s.compareTo(ans) > 0) continue; if (query(s)) ans = s; } return ans; } } 复制代码
- 时间复杂度：将所有 words[i]words[i] 存入字典树的复杂度为 O(\sum_{i = 0}^{n - 1}words[i].length)O(∑i=0n−1words[i].length)；查询每个 words[i]words[i] 是否合法的复杂度为 O(m)O(m)，其中 mm 为当前 words[i]words[i] 长度。整体复杂度为 O(\sum_{i = 0}^{n - 1}words[i].length)O(∑i=0n−1words[i].length)
- 空间复杂度：O(C)O(C)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.720 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
