Trie with DFS Search
Intuition
A trie (prefix tree) is ideal for storing words and performing prefix-based lookups. Each node has up to 26 children (one per letter) and a flag indicating whether a complete word ends at that node. Adding a word is a straightforward traversal, creating nodes as needed. Searching with wildcard support requires a depth-first search: for regular characters, we follow the corresponding child; for ., we try all existing children and succeed if any path matches the remaining pattern.
Algorithm
- **addWord:** Starting from the root, for each character create a child node if it does not exist, then move to that child. Mark the final node as a word ending.
- **search:** Implement a recursive DFS function taking the current node and position in the word.
- At each position, if the character is a letter, follow the corresponding child (return false if it does not exist).
- If the character is `.`, iterate over all non-null children and recursively search each one. Return true if any child path succeeds.
- When the end of the search word is reached, return whether the current node is marked as a word ending.
Time
O(m) for `addWord` where m is word length; O(26^m) worst case for `search` with all `.` characters, but typically much fasterSpaceO(n * m) where n is the number of words and m is average word lengthCode (C++ · Java · Python · Go)
class WordDictionary {
struct TrieNode {
TrieNode* children[26] = {};
bool isEnd = false;
};
TrieNode* root;
bool dfs(TrieNode* node, const string& word, int index) {
if (index == word.size()) return node->isEnd;
char c = word[index];
if (c == '.') {
for (int i = 0; i < 26; i++) {
if (node->children[i] && dfs(node->children[i], word, index + 1)) {
return true;
}
}
return false;
} else {
int idx = c - 'a';
if (!node->children[idx]) return false;
return dfs(node->children[idx], word, index + 1);
}
}
public:
WordDictionary() {
root = new TrieNode();
}
void addWord(string word) {
TrieNode* node = root;
for (char c : word) {
int idx = c - 'a';
if (!node->children[idx]) {
node->children[idx] = new TrieNode();
}
node = node->children[idx];
}
node->isEnd = true;
}
bool search(string word) {
return dfs(root, word, 0);
}
};class WordDictionary {
private class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isEnd = false;
}
private TrieNode root;
public WordDictionary() {
root = new TrieNode();
}
public void addWord(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null) {
node.children[idx] = new TrieNode();
}
node = node.children[idx];
}
node.isEnd = true;
}
public boolean search(String word) {
return dfs(root, word, 0);
}
private boolean dfs(TrieNode node, String word, int index) {
if (index == word.length()) return node.isEnd;
char c = word.charAt(index);
if (c == '.') {
for (int i = 0; i < 26; i++) {
if (node.children[i] != null && dfs(node.children[i], word, index + 1)) {
return true;
}
}
return false;
} else {
int idx = c - 'a';
if (node.children[idx] == null) return false;
return dfs(node.children[idx], word, index + 1);
}
}
}class WordDictionary:
def __init__(self):
self.children = {}
self.is_end = False
def addWord(self, word: str) -> None:
node = self
for c in word:
if c not in node.children:
node.children[c] = WordDictionary()
node = node.children[c]
node.is_end = True
def search(self, word: str) -> bool:
def dfs(node: "WordDictionary", index: int) -> bool:
if index == len(word):
return node.is_end
c = word[index]
if c == ".":
for child in node.children.values():
if dfs(child, index + 1):
return True
return False
else:
if c not in node.children:
return False
return dfs(node.children[c], index + 1)
return dfs(self, 0)type WordDictionary struct {
children [26]*WordDictionary
isEnd bool
}
func Constructor() WordDictionary {
return WordDictionary{}
}
func (wd *WordDictionary) AddWord(word string) {
node := wd
for _, c := range word {
idx := c - 'a'
if node.children[idx] == nil {
node.children[idx] = &WordDictionary{}
}
node = node.children[idx]
}
node.isEnd = true
}
func (wd *WordDictionary) Search(word string) bool {
return wd.dfs(word, 0)
}
func (wd *WordDictionary) dfs(word string, index int) bool {
if index == len(word) {
return wd.isEnd
}
c := word[index]
if c == '.' {
for i := 0; i < 26; i++ {
if wd.children[i] != nil && wd.children[i].dfs(word, index+1) {
return true
}
}
return false
}
idx := c - 'a'
if wd.children[idx] == nil {
return false
}
return wd.children[idx].dfs(word, index+1)
}