Leetcode.208.Implement Trie (Pre
2019-11-27 本文已影响0人
Jimmy木
题目
自定义一个树,实现树的插入字符串, 查找字符串, 是否有包含前缀的字符串。
字符串只包含a-z。
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // returns true
trie.search("app"); // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app"); // returns true
思路1
使用set。插入和查找都有系统方法。判断前缀通过二分法查找,效率还是太低。
class Trie {
public:
set<string> m_set;
/** Initialize your data structure here. */
Trie() {
}
/** Inserts a word into the trie. */
void insert(string word) {
m_set.insert(word);
}
/** Returns if the word is in the trie. */
bool search(string word) {
return m_set.count(word) > 0;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
vector<string> vec(m_set.begin(), m_set.end());
int l = 0, r = (int)vec.size()-1;
while (l <= r) {
int mid = (l + r) / 2;
string s = vec[mid];
if (s.substr(0,prefix.size()) == prefix) {
return true;
}else if (s.substr(0,prefix.size()) > prefix) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return false;
}
};
思路2
由于只包含a~z
的字符,所以可以建立一个26维的数结构,分支都是a~z的字符,通过一个结束标识符判断是否是一个完整的字符串。
挺巧妙的一种设计结构,适合查找前缀这种场景。
class Trie {
public:
struct TrieNode {
TrieNode *ch[26] = {nullptr};
bool isEnd;
};
TrieNode *root = nullptr;
Trie() {
root = new TrieNode();
}
void insert(string word) {
TrieNode *temp = root;
for (char c : word) {
if (temp->ch[c-'a'] == nullptr) {
temp->ch[c-'a'] = new TrieNode();
}
temp = temp->ch[c-'a'];
}
temp->isEnd = true;
}
bool search(string word) {
TrieNode *temp = root;
for(char c : word) {
if (temp->ch[c-'a'] == nullptr) {
return false;
}
temp = temp->ch[c-'a'];
}
return temp->isEnd;
}
bool startsWith(string prefix) {
TrieNode *temp = root;
for(char c : prefix) {
if (temp->ch[c-'a'] == nullptr) {
return false;
}
temp = temp->ch[c-'a'];
}
return true;
}
};
总结
n维树的实现,学习了多维树的使用。