題目描述
這是 LeetCode 上的 676. 實(shí)現(xiàn)一個(gè)魔法字典 ，難度為 中等函筋。
Tag : 「字典樹」沙合、「DFS」
設(shè)計(jì)一個(gè)使用單詞列表進(jìn)行初始化的數(shù)據(jù)結(jié)構(gòu)，單詞列表中的單詞 互不相同 驻呐。 如果給出一個(gè)單詞灌诅，請(qǐng)判定能否只將這個(gè)單詞中一個(gè)字母換成另一個(gè)字母，使得所形成的新單詞存在于你構(gòu)建的字典中含末。
實(shí)現(xiàn) MagicDictionary 類：
-
MagicDictionary()初始化對(duì)象 -
void buildDict(String[] dictionary)使用字符串?dāng)?shù)組dictionary設(shè)定該數(shù)據(jù)結(jié)構(gòu)猜拾，dictionary中的字符串互不相同 -
bool search(String searchWord)給定一個(gè)字符串searchWord，判定能否只將字符串中 一個(gè) 字母換成另一個(gè)字母佣盒，使得所形成的新字符串能夠與字典中的任一字符串匹配挎袜。如果可以，返回true肥惭；否則盯仪，返回false。
示例：
輸入
["MagicDictionary", "buildDict", "search", "search", "search", "search"]
[[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
輸出
[null, null, false, true, false, false]
解釋
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict(["hello", "leetcode"]);
magicDictionary.search("hello"); // 返回 False
magicDictionary.search("hhllo"); // 將第二個(gè) 'h' 替換為 'e' 可以匹配 "hello" 蜜葱，所以返回 True
magicDictionary.search("hell"); // 返回 False
magicDictionary.search("leetcoded"); // 返回 False
提示：
-
dictionary[i]僅由小寫英文字母組成 -
dictionary中的所有字符串 互不相同 -
searchWord僅由小寫英文字母組成 -
buildDict僅在search之前調(diào)用一次 - 最多調(diào)用
次
search
Trie + DFS
為了方便全景，我們令 dictionary 為 ss，令 searchWord 為 s牵囤。
整體題意：給定字符串 s爸黄，問能否存在替換掉 s 中的某個(gè)字符滞伟，使得新字符串出現(xiàn)在 ss 數(shù)組中。
考慮如何使用「字典樹/Trie」求解該問題：
buildDict操作：我們可以將所有的存入字典樹中炕贵，方便后續(xù)檢索梆奈；
search操作：設(shè)計(jì)遞歸函數(shù)boolean query(String s, int idx, int p, int limit)，其中s為待檢索的字符串称开，idx為當(dāng)前處理到字符串s的哪一位亩钟，p為當(dāng)前搜索到字典樹的索引編號(hào)（起始有），
limit為當(dāng)前剩余的替換字符次數(shù)鳖轰，根據(jù)題意清酥，limit固定為，含義為必須替換掉
s的一個(gè)字符脆霎。
對(duì)于而言总处，我們可以枚舉新字符串在當(dāng)前位置是何種字符（
個(gè)選擇），若當(dāng)前枚舉到的字符與
爆搜過程中替換次數(shù)為負(fù)數(shù)直接剪枝，當(dāng)爆搜到結(jié)尾位置忆肾，再檢查當(dāng)前的字典樹索引是否為單詞結(jié)尾節(jié)點(diǎn)（對(duì)應(yīng)查詢數(shù)組
ss中是否存在該字符串）荸频，以及剩余的替換次數(shù)limit是否為。
不了解「Trie / 字典樹」的同學(xué)可以看前置 ??：字典樹入門客冈。里面通過圖例展示了字典樹基本形態(tài)旭从，以及提供了「數(shù)組實(shí)現(xiàn)」和「TrieNode 實(shí)現(xiàn)」兩種方式，還有「數(shù)組大小估算方式」和「Trie 應(yīng)用面」介紹
代碼：
class MagicDictionary {
int N = 100 * 100, M = 26, idx = 0;
int[][] tr = new int[N][M];
boolean[] isEnd = new boolean[N * M];
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;
}
boolean query(String s, int idx, int p, int limit) {
if (limit < 0) return false;
if (idx == s.length()) return isEnd[p] && limit == 0;
int u = s.charAt(idx) - 'a';
for (int i = 0; i < 26; i++) {
if (tr[p][i] == 0) continue;
if (query(s, idx + 1, tr[p][i], i == u ? limit : limit - 1)) return true;
}
return false;
}
public void buildDict(String[] ss) {
for (String s : ss) add(s);
}
public boolean search(String s) {
return query(s, 0, 0, 1);
}
}
- 時(shí)間復(fù)雜度：
buildDict操作需要將所有字符存入Trie场仲，復(fù)雜度為和悦；
search操作在不考慮limit以及字典樹中最多只有個(gè)方案渠缕，其中
為搜索字符串的最大長度
- 空間復(fù)雜度：
，其中
為存入
Trie的最大方案數(shù)亦鳞，
最后
這是我們「刷穿 LeetCode」系列文章的第 No.676 篇，系列開始于 2021/01/01燕差，截止于起始日 LeetCode 上共有 1916 道題目遭笋，部分是有鎖題，我們將先把所有不帶鎖的題目刷完徒探。
在這個(gè)系列文章里面瓦呼，除了講解解題思路以外，還會(huì)盡可能給出最為簡潔的代碼测暗。如果涉及通解還會(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ā)布
