醉后不知天在水
满船清梦压星河
C++，字典树，实际上本题目就是创造一颗字典树。
创造一颗字典树其实是很简单的，直接构造多叉树就好了，首先得确定多叉树的结点应该是这样的：
struct Node {
vector<Node *> nexts;
char value;
bool has_end;
Node(char x) : value(x), has_end(false), nexts(vector<Node *> (0)) {};
};
根结点不记录任何字母。所以对应的插入操作就是:
- 对于每个新的字母，首先判断结点的
nexts域中是否与其有相等的 - 如果没有相等的或者是为空，则需要创建新的结点
- 因为存在某些情况下会插入某些比已存在字符串更短的字符串，比如先插入“23333”，又插入了“2333”，这个时候需要进行标记，判断在当前结点是否真的是字符串结尾
对应的查找和前缀匹配就很简单了，就是一层一层对应就好了。
代码如下：
class Trie {
public:
/** Initialize your data structure here. */
Trie() {
root = new Node('R');
}
/** Inserts a word into the trie. */
void insert(string word) {
int index = 0;
Node *curr = root;
for (char it : word) {
bool get_next = false;
for (auto next : curr->nexts) {
if (next->value == it) {
curr = next;
get_next = true;
break;
}
}
if (!get_next) {
Node *next = new Node(it);
curr->nexts.push_back(next);
curr = next;
}
}
curr->has_end = true;
}
/** Returns if the word is in the trie. */
bool search(string word) {
Node *curr = root;
for (auto it : word) {
Node *next = nullptr;
for (auto node_it : curr->nexts) {
if (node_it->value == it)
next = node_it;
}
if (next)
curr = next;
else return false;
}
if (curr->nexts.empty() || curr->has_end)
return true;
else
return false;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
Node *curr = root;
bool ans = true;
for (char it : prefix) {
Node *next = nullptr;
for (auto node_it : curr->nexts) {
if (node_it->value == it)
next = node_it;
}
if (next)
curr = next;
else return false;
}
return true;
}
private:
struct Node {
vector<Node *> nexts;
char value;
bool has_end;
Node(char x) : value(x), has_end(false), nexts(vector<Node *> (0)) {};
};
Node *root;
};
/**
* 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);
*/
