Re: [閒聊] 每日LeetCode
看板Marginalman作者NTHUlagka (拉卡)時間2年前發表 (2023/03/19 06:17), 2年前編輯推噓1(1推 0噓 2→)留言3則, 2人參與, 2年前最新討論串266/719 (看更多)
211. Design Add and Search Words Data Structure
設計一個系統可以支援加新字(addWord)以及搜尋(search)字是否在系統的功能
具體來說就是要實作一個WordDictionary的類別，並有以下幾個函數
1. WordDictionary: 初始化WordDictionary物件
2. void addWord(word): 加word到設計的系統中，以便做後續查找的功能
3. bool search(word): 從系統中找是否有符合word的字被加入，特別需要注意word中可
能會有'.'字元，代表的意思是可以是任何字母，也就是如果word是"w.a"則"waa" ~ "wza
"都是符合的答案
例子:
輸入
["WordDictionary","addWord","addWord","addWord","search","search","search","se
arch"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
輸出
[null,null,null,null,false,true,true,true]
解釋:
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True
限制
1: 每個字的長度，大於等於1，小於等於25
2, 3: word在addWord或是search的函數中只會有小寫字母
4: 最多只會有三個'.'在search函數的參數word中
5: 最多只會呼叫addWord和search各10^4次
解題想法:
看到字串查找，我第一個想法就是Trie，那至於如何去支援search就得依靠dfs的思維去
遞迴查找答案
以這樣的做法底下，時間複雜度addWord最多就是25 * 10^4,而search就會是25*25*25*10
^4，這複雜度其實是會TLE，不知道有沒有更快的做法，反正我是想不到orz
C++ code
-----------------------------------------------------------------
struct Trie {
Trie *child[26];
bool isWord = false;
};
class WordDictionary {
public:
Trie* root= new Trie();
WordDictionary() {}
void addWord(string word) {
auto cur = root;
for(auto &w : word) {
if(!cur->child[w - 'a'])
cur->child[w - 'a'] = new Trie();
cur = cur->child[w - 'a'];
}
cur->isWord = true;
}
bool search(string word) {
return dfs(root, word, 0);
}
bool dfs(Trie *cur, string& word, int i) {
if(!cur) return false;
if(i == word.size()) return cur->isWord;
if(word[i] == '.') {
bool ret = false;
for(int j=0; j<26 && !ret; j++)
ret |= dfs(cur->child[j], word, i + 1);
return ret;
} else
return dfs(cur->child[word[i] - 'a'], word, i + 1);
}
};
-----------------------------------------------------------------
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.79.189.98 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1679206664.A.5B8.html
※ 編輯: NTHUlagka (42.79.189.98 臺灣), 03/19/2023 14:20:20
→
03/19 14:21,
2年前
, 1F
03/19 14:21, 1F
※ 編輯: NTHUlagka (42.79.189.98 臺灣), 03/19/2023 14:38:42
推
03/19 16:56,
2年前
, 2F
03/19 16:56, 2F
→
03/19 16:56,
2年前
, 3F
03/19 16:56, 3F
嗯嗯那就合理了
※ 編輯: NTHUlagka (42.79.189.98 臺灣), 03/19/2023 17:37:57
討論串 (同標題文章)
完整討論串 (本文為第 266 之 719 篇)：
閒聊
1
3