# LeetCode Medium 208. Implement Trie (Prefix Tree)
tags: leetcode
旅行で東京を離れていました.何もしていませんでした.何もしないと本当に何がしたいか自ずと分かってくるので良いかも知れません.
問題
アイデア
Trieとは文字列を高速に検索するためのN-aryの木構造のことです.応用先は自動補完,スペルチェッカーなどです.
実装するのは以下のメソッドです.
insert(word)
:word
をTrieに挿入するsearch(word)
:word
がTrieに入っているか真偽値を返すstartsWith(prefix)
:prefix
で始まる語がTrieに入っているか真偽値を返す
注意点としては以下の通りです.
a-z
で構成された文字列のみ入力として与えられる- 空文字列は入力されない
解法
Hashmapを使って実装をします.
1文字ずつ走査して,それぞれの文字がノードが結びつくようにします.次のように書けば良いです.
unordered_map<char, TrieNode*>
クラスTrieNode
ではそのノードで終わるword
があるかどうかを判定するbool
値isEnd
を保持するようにします.
実装は定義に忠実にします.
計算量
検索するword
の長さをN
とします.また,prefix
の長さをM
とします.
- 時間計算量
- コンストラクタには$O(1)$
insert
,search
には$O(N)$startsWith
には$O(M)$
- 空間計算量
std::unordered_map
を使っているので,最悪でも入力の文字列の長さ分しか空間は使いません.- もし
std::vector
などを使って実装をすると入力の文字列の最長をmaxLen
として,$26^{maxLen}$の空間が必要となり効率が悪いです.
- もし
insert
の最悪計算量は$O(N)$
C++
class TrieNode { public: unordered_map<char, TrieNode*> children; bool isEnd; TrieNode(): isEnd(false) {} }; class Trie { private: TrieNode* root; public: /** Initialize your data structure here. */ Trie() { root = new TrieNode(); } /** Inserts a word into the trie. */ void insert(string word) { auto cur = root; for (auto& ch: word) { if (cur->children.find(ch) == end(cur->children)) cur->children[ch] = new TrieNode(); cur = cur->children[ch]; } cur->isEnd = true; } /** Returns if the word is in the trie. */ bool search(string word) { auto cur = root; for (auto& ch : word) { if (cur->children.find(ch) == end(cur->children)) return false; cur = cur->children[ch]; } return cur->isEnd; } /** Returns if there is any word in the trie that starts with the given prefix. */ bool startsWith(string prefix) { auto cur = root; for (auto& ch : prefix) { if (cur->children.find(ch) == end(cur->children)) return false; cur = cur->children[ch]; } return true; } }; /** * Your Trie object will be instantiated and called as such: * Trie* obj = new Trie(); * obj->insert(word); * bool param_2 = obj->search(word); * bool param_3 = obj->startsWith(prefix); */