題目描述
這是 LeetCode 上的 720. 詞典中最長的單詞 ，難度為 簡(jiǎn)單。
Tag : 「模擬」、「哈希表」蚪黑、「字典樹」
給出一個(gè)字符串?dāng)?shù)組 words 組成的一本英語詞典。返回 words 中最長的一個(gè)單詞中剩，該單詞是由 words 詞典中其他單詞逐步添加一個(gè)字母組成。
若其中有多個(gè)可行的答案抒寂，則返回答案中字典序最小的單詞结啼。若無答案，則返回空字符串屈芜。
示例 1：
輸入：words = ["w","wo","wor","worl", "world"]
輸出："world"
解釋： 單詞"world"可由"w", "wo", "wor", 和 "worl"逐步添加一個(gè)字母組成郊愧。
示例 2：
輸入：words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
輸出："apple"
解釋："apply" 和 "apple" 都能由詞典中的單詞組成朴译。但是 "apple" 的字典序小于 "apply"
提示：
- 所有輸入的字符串
都只包含小寫字母。
模擬
數(shù)據(jù)范圍很小属铁，我們可以直接模擬來做眠寿。
先將所有的 存入
Set 集合，方便后續(xù)可以近似 查詢某個(gè)子串是否存在
中焦蘑。
遍歷 數(shù)組（題目沒有說
不重復(fù)盯拱，因此最好遍歷剛剛預(yù)處理的
Set 集合），判斷每個(gè) 是否為「合法單詞」例嘱，同時(shí)利用當(dāng)前的最長單詞來做剪枝狡逢。
不算剪枝效果，該做法計(jì)算量不超過 拼卵，可以過奢浑。
代碼：
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;
}
}
- 時(shí)間復(fù)雜度：預(yù)處理
Set集合復(fù)雜度近似；判斷某個(gè)
中腋腮，復(fù)雜度為
雀彼，其中
為字符串長度，處理
compareTo操作即寡，其復(fù)雜度為徊哑，其中
和
為參與比較的兩字符串長度，該操作相比于生成子串可忽略嘿悬，而對(duì)于一個(gè)長度為
，末項(xiàng)為
- 空間復(fù)雜度：
Trie
上述解法中「枚舉某個(gè) 的所有子串，并判斷子串是否在
數(shù)組中出現(xiàn)」的操作可使用「字典樹」來實(shí)現(xiàn)钢拧。
不了解「Trie / 字典樹」的同學(xué)可以看前置 ??：字典樹入門蟹漓。里面通過圖例展示了字典樹基本形態(tài)，以及提供了「數(shù)組實(shí)現(xiàn)」和「TrieNode 實(shí)現(xiàn)」兩種方式源内，還有「數(shù)組大小估算方式」和「Trie 應(yīng)用面」介紹葡粒。
回到本題，起始先將所有的 存入字典樹膜钓，并記錄每個(gè)字符的結(jié)尾編號(hào)嗽交。
對(duì)于某個(gè) 而言，其能成為「合法單詞」的充要條件為：
的每個(gè)前綴編號(hào)都有「以結(jié)尾編號(hào)」所被記錄颂斜。
一些細(xì)節(jié)：為了防止每個(gè)樣例都
new大數(shù)組夫壁，我們使用static進(jìn)行優(yōu)化，并在跑樣例前進(jìn)行相應(yīng)的清理工作沃疮。
代碼：
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;
}
}
- 時(shí)間復(fù)雜度：將所有
盒让；查詢每個(gè)
梅肤，其中
- 空間復(fù)雜度：
最后
這是我們「刷穿 LeetCode」系列文章的第 No.720 篇邑茄，系列開始于 2021/01/01姨蝴，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題肺缕，我們將先把所有不帶鎖的題目刷完左医。
在這個(gè)系列文章里面，除了講解解題思路以外搓谆，還會(huì)盡可能給出最為簡(jiǎn)潔的代碼炒辉。如果涉及通解還會(huì)相應(yīng)的代碼模板。
為了方便各位同學(xué)能夠電腦上進(jìn)行調(diào)試和提交代碼泉手，我建立了相關(guān)的倉庫：https://github.com/SharingSource/LogicStack-LeetCode 黔寇。
在倉庫地址里，你可以看到系列文章的題解鏈接斩萌、系列文章的相應(yīng)代碼缝裤、LeetCode 原題鏈接和其他優(yōu)選題解。
更多更全更熱門的「筆試/面試」相關(guān)資料可訪問排版精美的 合集新基地 ????
本文由mdnice多平臺(tái)發(fā)布
