Array-Based Trie Node
Intuition
The classic trie implementation uses an array of 26 pointers (one for each lowercase letter) at each node, plus a boolean flag to mark the end of a word. To insert a word, we traverse from the root, creating new nodes as needed for each character. To search, we follow the character path and check the end-of-word flag. For prefix search, we follow the same path but do not require the end-of-word flag. This approach offers O(1) character lookups at each level at the cost of higher memory usage.
Algorithm
- Each trie node has an array of 26 child pointers (initialized to null) and an `isEnd` boolean.
- **Insert:** For each character in the word, compute its index (char - 'a'). If the child at that index is null, create a new node. Move to the child. After the last character, mark the node as end-of-word.
- **Search:** For each character, follow the child pointer. If any is null, return false. After the last character, return the isEnd flag.
- **StartsWith:** Same as search, but return true if we reach the end of the prefix without encountering a null pointer (regardless of isEnd).
Time
O(m) per operation where m is the length of the word or prefixSpaceO(n * m) where n is the number of words and m is the average word lengthCode (C++ · Java · Python · Go)
class Trie {
private:
struct TrieNode {
TrieNode* children[26] = {};
bool isEnd = false;
};
TrieNode* root;
public:
Trie() {
root = new TrieNode();
}
void insert(string word) {
TrieNode* node = root;
for (char c : word) {
int idx = c - 'a';
if (node->children[idx] == nullptr) {
node->children[idx] = new TrieNode();
}
node = node->children[idx];
}
node->isEnd = true;
}
bool search(string word) {
TrieNode* node = findNode(word);
return node != nullptr && node->isEnd;
}
bool startsWith(string prefix) {
return findNode(prefix) != nullptr;
}
private:
TrieNode* findNode(const string& s) {
TrieNode* node = root;
for (char c : s) {
int idx = c - 'a';
if (node->children[idx] == nullptr) return nullptr;
node = node->children[idx];
}
return node;
}
};class Trie {
private int[][] children;
private boolean[] isEnd;
private int count;
public Trie() {
children = new int[60001][26];
isEnd = new boolean[60001];
count = 0;
for (int[] row : children) {
Arrays.fill(row, -1);
}
}
public void insert(String word) {
int node = 0;
for (char c : word.toCharArray()) {
int idx = c - 'a';
if (children[node][idx] == -1) {
count++;
children[node][idx] = count;
}
node = children[node][idx];
}
isEnd[node] = true;
}
public boolean search(String word) {
int node = findNode(word);
return node != -1 && isEnd[node];
}
public boolean startsWith(String prefix) {
return findNode(prefix) != -1;
}
private int findNode(String s) {
int node = 0;
for (char c : s.toCharArray()) {
int idx = c - 'a';
if (children[node][idx] == -1) return -1;
node = children[node][idx];
}
return node;
}
}class Trie:
def __init__(self):
self.children = {}
self.is_end = False
def insert(self, word: str) -> None:
node = self
for c in word:
if c not in node.children:
node.children[c] = Trie()
node = node.children[c]
node.is_end = True
def search(self, word: str) -> bool:
node = self._find(word)
return node is not None and node.is_end
def startsWith(self, prefix: str) -> bool:
return self._find(prefix) is not None
def _find(self, s: str):
node = self
for c in s:
if c not in node.children:
return None
node = node.children[c]
return nodetype Trie struct {
children [26]*Trie
isEnd bool
}
func Constructor() Trie {
return Trie{}
}
func (t *Trie) Insert(word string) {
node := t
for _, c := range word {
idx := c - 'a'
if node.children[idx] == nil {
node.children[idx] = &Trie{}
}
node = node.children[idx]
}
node.isEnd = true
}
func (t *Trie) Search(word string) bool {
node := t.find(word)
return node != nil && node.isEnd
}
func (t *Trie) StartsWith(prefix string) bool {
return t.find(prefix) != nil
}
func (t *Trie) find(s string) *Trie {
node := t
for _, c := range s {
idx := c - 'a'
if node.children[idx] == nil {
return nil
}
node = node.children[idx]
}
return node
}