# LeetCode Implement Trie (Prefix Tree)

LeetCode Implement Trie (Prefix Tree)
Implement a trie with `insert`, `search`, and `startsWith` methods.
Note:
You may assume that all inputs are consist of lowercase letters `a-z`.

```const int MAXN = 26;
class Trie {
private:
struct Node
{
char c;
bool isWord;
Node(char c_, bool isWord_) :c(c_), isWord(isWord_) {
for (int i = 0; i < MAXN; ++i)children.push_back(NULL);
};
vector<Node*> children;
};
Node *root;
public:
/** Initialize your data structure here. */
Trie() {
root = new Node(' ', true);
}
/** Inserts a word into the trie. */
void insert(string word) {
Node *cur = root;
for (int i = 0; i < word.size(); ++i) {
int idx = word[i] - 'a';
if (cur->children[idx] == NULL)cur->children[idx] = new Node(word[i], false);
cur = cur->children[idx];
}
cur->isWord = true;
}
/** Returns if the word is in the trie. */
bool search(string word) {
Node *cur = root;
for (int i = 0; i < word.size(); ++i) {
int idx = word[i] - 'a';
if (cur->children[idx] == NULL)return false;
cur = cur->children[idx];
}
return cur->isWord;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
Node *cur = root;
for (int i = 0; i < prefix.size(); ++i) {
int idx = prefix[i] - 'a';
if (cur->children[idx] == NULL)return false;
cur = cur->children[idx];
}
return true;
}
};
```

## 1 thought on “LeetCode Implement Trie (Prefix Tree)”

This site uses Akismet to reduce spam. Learn how your comment data is processed.