題目描述
這是 LeetCode 上的 648. 單詞替換 ，難度為 中等。
Tag : 「字典樹」
在英語中，我們有一個叫做 詞根(root) 的概念，可以詞根后面添加其他一些詞組成另一個較長的單詞——我們稱這個詞為 繼承詞(successor)檩禾。例如，詞根an，跟隨著單詞 other(其他)略水，可以形成新的單詞 another(另一個)。
現(xiàn)在赤赊，給定一個由許多詞根組成的詞典 dictionary 和一個用空格分隔單詞形成的句子 sentence闯狱。你需要將句子中的所有繼承詞用詞根替換掉。如果繼承詞有許多可以形成它的詞根抛计，則用最短的詞根替換它哄孤。
你需要輸出替換之后的句子。
示例 1：
輸入：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
輸出："the cat was rat by the bat"
示例 2：
輸入：dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
輸出："a a b c"
提示：
-
dictionary[i]僅由小寫字母組成吹截。 -
sentence僅由小寫字母和空格組成瘦陈。 -
sentence中單詞的總量在范圍內。
-
sentence中每個單詞的長度在范圍 -
sentence中單詞之間由一個空格隔開晨逝。 -
sentence沒有前導或尾隨空格。
基本分析
這是一道 Trie 的模板題懦铺，還不了解 Trie 的同學可以先看前置 ??：【設計數(shù)據(jù)結構】實現(xiàn) Trie (前綴樹)
前置 ?? 通過圖解形式講解了 Trie 的結構與原理捉貌，以及提供了兩種實現(xiàn) Trie 的方式。
回到本題冬念，為了方便趁窃，我們令 ds 為 dictionary，令 s 為 sentence急前。
二維數(shù)組
一個比較習慣的做法醒陆，是使用「二維數(shù)組」來實現(xiàn) Trie，配合 static 優(yōu)化裆针，可以有效控制 new 的次數(shù)刨摩，耗時相對穩(wěn)定。
考慮兩個 Trie 的基本操作：
-
add操作：變量入?yún)⒆址?s据块，將字符串中的每位字符映射到码邻，同時為了能夠方便查詢某個字符串（而不只是某個前綴）是否曾經(jīng)存入過
Trie中，額外使用一個布爾數(shù)組isEnd記錄某個位置是否為單詞結尾另假。 -
query操作：
至于二維數(shù)組的大小估算像屋，可以直接開成 ，其中
為要插入到
Trie 中的字符總數(shù)边篮， 為對應的字符集大小己莺。在
沒有
MLE 風險時奏甫，可以直接開這么多；而當 較大（超過
凌受，甚至
時）阵子，可以適當將
中的
減少，使得總空間在
左右胜蛉，因為實際上由于二維數(shù)組中的某些行中會存儲一個字符以上挠进，實際上我們用不到這么多行。
代碼（不使用 static 優(yōu)化誊册，耗時增加十倍）：
class Solution {
static int N = 100000, M = 26;
static int[][] tr = new int[N][M];
static boolean[] isEnd = new boolean[N * M];
static int idx;
void add(String s) {
int p = 0;
for (int i = 0; i < s.length(); i++) {
int u = s.charAt(i) - 'a';
if (tr[p][u] == 0) tr[p][u] = ++idx;
p = tr[p][u];
}
isEnd[p] = true;
}
String query(String s) {
for (int i = 0, p = 0; i < s.length(); i++) {
int u = s.charAt(i) - 'a';
if (tr[p][u] == 0) break;
if (isEnd[tr[p][u]]) return s.substring(0, i + 1);
p = tr[p][u];
}
return s;
}
public String replaceWords(List<String> ds, String s) {
for (int i = 0; i <= idx; i++) {
Arrays.fill(tr[i], 0);
isEnd[i] = false;
}
for (String d : ds) add(d);
StringBuilder sb = new StringBuilder();
for (String str : s.split(" ")) sb.append(query(str)).append(" ");
return sb.substring(0, sb.length() - 1);
}
}
- 時間復雜度：令
领突，
為
s長度，復雜度為 - 空間復雜度：
案怯，其中
為字符集大小
TrieNode
另外一個能夠有效避免「估數(shù)組大小」操作的方式君旦，是使用 TrieNode 的方式實現(xiàn) Trie：每次使用到新的格子再觸發(fā) new 操作。
至于為什么有了 TrieNode 的方式嘲碱，我還是會采用「二維數(shù)組」優(yōu)先的做法金砍，在 知乎 上有同學問過我類似的問題，只不過原問題是「為什么有了動態(tài)開點線段樹麦锯，直接 build 出 空間的做法仍有意義」恕稠，這對應到本題使用「二維數(shù)組」還是「TrieNode」是一樣的道理：
除非某些語言在啟動時，采用虛擬機的方式扶欣，并且預先分配了足夠的內存谱俭，否則所有的 new 操作都需要反映到 os 上，而在 linux 分配時需要遍歷紅黑樹宵蛀，因此即使是總空間一樣昆著，一次性的 new 要比多次小空間的 new 更省時間，同時集中性的 new 也比分散性的 new 操作要更快术陶，這也就是為什么我們不無腦使用 TrieNode 的原因凑懂。
代碼：
class Solution {
class Node {
boolean isEnd;
Node[] tns = new Node[26];
}
Node root = new Node();
void add(String s) {
Node p = root;
for (int i = 0; i < s.length(); i++) {
int u = s.charAt(i) - 'a';
if (p.tns[u] == null) p.tns[u] = new Node();
p = p.tns[u];
}
p.isEnd = true;
}
String query(String s) {
Node p = root;
for (int i = 0; i < s.length(); i++) {
int u = s.charAt(i) - 'a';
if (p.tns[u] == null) break;
if (p.tns[u].isEnd) return s.substring(0, i + 1);
p = p.tns[u];
}
return s;
}
public String replaceWords(List<String> ds, String s) {
for (String str : ds) add(str);
StringBuilder sb = new StringBuilder();
for (String str : s.split(" ")) sb.append(query(str)).append(" ");
return sb.substring(0, sb.length() - 1);
}
}
- 時間復雜度：令
s長度梧宫，復雜度為 - 空間復雜度：
加餐
今天額外增加一道更貼合筆試面試的加餐題 : 結合 DFS 的 Trie 運用題 ????
最后
這是我們「刷穿 LeetCode」系列文章的第 No.648 篇，系列開始于 2021/01/01塘匣，截止于起始日 LeetCode 上共有 1916 道題目脓豪，部分是有鎖題，我們將先把所有不帶鎖的題目刷完忌卤。
在這個系列文章里面扫夜，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模板笤闯。
為了方便各位同學能夠電腦上進行調試和提交代碼堕阔，我建立了相關的倉庫：https://github.com/SharingSource/LogicStack-LeetCode 。
在倉庫地址里颗味，你可以看到系列文章的題解鏈接超陆、系列文章的相應代碼、LeetCode 原題鏈接和其他優(yōu)選題解浦马。
更多更全更熱門的「筆試/面試」相關資料可訪問排版精美的 合集新基地 ????
本文由mdnice多平臺發(fā)布
