Problem

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

  • WordDictionary() Initializes the object.
  • void addWord(word) Adds word to the data structure, it can be matched later.
  • bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

Input:
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output:
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

Solution

Video explanation

See linked video for a walk-through of trie search variants.

Method 1 - Brute Force Linear Scan (Store Words in List/Set)

Intuition

Keep every added word in a plain list (or array). To answer a search(pattern) we test the pattern against each stored word. The wildcard . only affects per‑character comparison; no preprocessing is needed. This is the simplest design but scales poorly when the number of words grows.

Approach

  1. Maintain a dynamic list words.
  2. addWord(word): append word to words.
  3. search(pattern):
    • Let L = len(pattern). Iterate each w in words.
    • Skip if len(w) != L.
    • For each position i from 0..L-1:
      • If pattern[i] == '.' continue (wildcard matches any single char).
      • Else if pattern[i] != w[i] -> not a match; break.
    • If all positions match, return true.
  4. If no word matches, return false.

Complexity

  • ⏰ Time complexity:
    • addWord: O(1) amortized append for list or O(L) for set as we have to calculate hashCode before saving in set.
    • search
      • exact: O(N * L) for list as scans all words OR O(L) for set
      • search with '.' wildcards: still O(N * L) worst case because every position may need checking against each word.
  • 🧺 Space complexity: O(N * L) total characters stored; only O(1) auxiliary space per query.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class WordDictionary {
    private final List<String> words = new ArrayList<>();

    public WordDictionary() {}

    public void addWord(String word) {
        words.add(word);
    }

    public boolean search(String pattern) {
        int L = pattern.length();
        outer: for (String w : words) {
            if (w.length() != L) continue;
            for (int i = 0; i < L; i++) {
                char pc = pattern.charAt(i);
                if (pc != '.' && pc != w.charAt(i)) {
                    continue outer;
                }
            }
            return true;
        }
        return false;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class WordDictionary:
    def __init__(self) -> None:
        self.words: list[str] = []

    def addWord(self, word: str) -> None:
        self.words.append(word)

    def search(self, pattern: str) -> bool:
        L = len(pattern)
        for w in self.words:
            if len(w) != L:
                continue
            for i in range(L):
                if pattern[i] != '.' and pattern[i] != w[i]:
                    break
            else:
                return True
        return False

Method 2 - Trie with Map Children (Substring-Based DFS)

Intuition

Instead of re-checking unrelated words, a Trie groups words by shared prefixes. Each node represents a prefix; descending one character at a time prunes huge portions of the search space. The wildcard . forces branching: we must explore all child nodes at that position. This version uses word.substring(1) at each recursive step for simplicity, trading speed/memory for cleaner code.

Approach

  1. Node structure: TrieNode holds a Map<Character, TrieNode> children and a boolean isEndOfWord.
  2. addWord(word): Walk characters; create missing child nodes; mark end node.
  3. search(pattern): Call searchInNode(pattern, node) starting at root.
    • Base: Empty pattern -> return node.isEndOfWord.
    • Let c = pattern[0].
    • If c == '.': recurse into every child with pattern.substring(1); return true if any succeeds.
    • Else: follow matching child; if absent return false; recurse with substring(1).
  4. Return the result of the initial call.

Complexity

  • ⏰ Time complexity: addWord: O(L) traverse/create nodes; search exact: O(L) follow one path; search pattern: O(b^k * L) worst case where k = number of '.' wildcard positions in the query (each can branch to up to b ≤ 26 children). Substring creation adds O(L) per level yielding O(b^k * L^2) in the pathological case.
  • 🧺 Space complexity: O(N * L) nodes across all inserted words (one per unique prefix) plus recursion stack O(L) and transient substrings up to O(L^2) worst case.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

public class WordDictionary {
	static class TrieNode {
		Map<Character, TrieNode> children = new HashMap<Character, TrieNode> ();
		boolean isEndOfWord;
	}
    private final TrieNode root;

    public WordDictionary() {
        root = new TrieNode();
    }
	  
    // Adds a word into the data structure.
    public void addWord(String word) {
        TrieNode curr = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (!curr.children.containsKey(c)) {
                curr.children.put(c, new TrieNode());
            }
            curr = curr.children.get(c);
        }
        curr.isEndOfWord = true;
    }

    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    public boolean search(String word) {
        return searchInNode(word, root);
    }

    private boolean searchInNode(String word, TrieNode node) {
        if (word == null || (word.isEmpty())) {
            return node.isEndOfWord;
        }
        char c = word.charAt(0);
        if (c == '.') {
            for (TrieNode child : node.children.values()) {
                if (searchInNode(word.substring(1), child)) {
                    return true;
                }
            }
        }
        //if character is neither equal to the node nor '.', return false
        if (!node.children.containsKey(c)) {
            return false;
        }
        return searchInNode(word.substring(1), node.children.get(c));
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class TrieNode:
	def __init__(self):
		self.children: dict[str, TrieNode] = {}
		self.is_end_of_word = False

class WordDictionary:
	def __init__(self):
		self.root = TrieNode()

	def addWord(self, word: str) -> None:
		curr = self.root
		for c in word:
			if c not in curr.children:
				curr.children[c] = TrieNode()
			curr = curr.children[c]
		curr.is_end_of_word = True

	def search(self, pattern: str) -> bool:
		def searchInNode(node: TrieNode, s: str) -> bool:
			if not s:
				return node.is_end_of_word
			c = s[0]
			if c == '.':
				for child in node.children.values():
					if searchInNode(child, s[1:]):
						return True
				return False
			if c not in node.children:
				return False
			return searchInNode(node.children[c], s[1:])

		return searchInNode(self.root, pattern)

Method 3 - Trie with Map Children (Index-Based DFS, No Substrings)

Intuition

Method 2 pays an extra cost creating substring objects at every recursion level. We can avoid that by passing an index into the original pattern string, reducing both time and memory overhead. Logic is identical; only parameterization changes.

Approach

  1. Use the same TrieNode shape as Method 2.
  2. addWord unchanged.
  3. search(pattern) invokes searchInNode(node, pattern, i) with i = 0.
  4. Recurrence:
    • If i == len(pattern): return node.isEndOfWord.
    • Let c = pattern[i].
    • If c == '.': iterate all children; if any recursive call with i+1 returns true -> propagate true.
    • Else: fetch child node.children.get(c); if missing return false; recurse with i+1.
  5. Return result of initial call.

Complexity

  • ⏰ Time complexity:
    • addWord: O(L) as insertion is simple down the path;
    • search exact: O(L);
    • search pattern: O(N * L) as we may have to go through whole of trie, but if the trie is complete, then it can be O(a^L), where is alphabet size, which is 26 for this problem.
  • 🧺 Space complexity: O(N * L) for trie nodes; recursion stack O(L); auxiliary O(1) per frame (no substring allocations).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

public class WordDictionary {
	static class TrieNode {
		Map<Character, TrieNode> children = new HashMap<Character, TrieNode> ();
		boolean isEndOfWord;
	}
    private final TrieNode root;

    public WordDictionary() {
        root = new TrieNode();
    }
	  
    // Adds a word into the data structure.
    public void addWord(String word) {
        TrieNode curr = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (!curr.children.containsKey(c)) {
                curr.children.put(c, new TrieNode());
            }
            curr = curr.children.get(c);
        }
        curr.isEndOfWord = true;
    }

    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
	public boolean search(String word) {
		return searchInNode(word, 0, root);
	}
	
	private boolean searchInNode(String word, int index, TrieNode node) {
		if (index == word.length()) {
			return node.isEndOfWord;
		}
		
		char c = word.charAt(index);
		if (c == '.') {
			for (TrieNode child : node.children.values()) {
				if (searchInNode(word, index+1, child)) {
					return true;
				}
			}
			return false;
		}
		
		//if character at indexition 'index' is neither equal to the node nor '.', return false
		if (!node.children.containsKey(word.charAt(index))) {
			return false;
		}
	
		return searchInNode(word, index + 1, node.children.get(c));
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class TrieNode:
    def __init__(self):
        self.children: dict[str, TrieNode] = {}
        self.is_end_of_word = False

class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        curr = self.root
        for c in word:
            if c not in curr.children:
                curr.children[c] = TrieNode()
            curr = curr.children[c]
        curr.is_end_of_word = True

    def search(self, word: str) -> bool:
        def search_in_node(index: int, node: TrieNode) -> bool:
            if not node:
                return False
            if index == len(word):
                return node.is_end_of_word

            char = word[index]
            if char == '.':
                for child in node.children.values():
                    if search_in_node(index + 1, child):
                        return True
                return False
            else:
                if char not in node.children:
                    return False
                return search_in_node(index + 1, node.children[char])

        return search_in_node(0, self.root)

Method 4 - Trie with Fixed Array Children (26-Way Branching)

Intuition

When the alphabet is known and small (lowercase English letters), a fixed array of size 26 per node replaces the hash map. This removes hash overhead and can speed up traversal at the cost of allocating 26 slots per node (even if sparse). Memory trade‑off vs Method 2/3: faster constant factors, higher baseline space for few children.

Approach

  1. Node: TrieNode holds TrieNode[26] children and boolean isEndOfWord.
  2. addWord(word):
    • For each character c, compute idx = c - 'a'.
    • Create child if null; advance.
    • After last char set isEndOfWord = true.
  3. search(pattern) calls searchInNode(node, pattern, i) similar to Method 3.
  4. In recursion:
    • If end reached, return isEndOfWord.
    • If pattern[i] == '.' iterate all 26 child slots (skip nulls) and recurse.
    • Else compute index and follow single child.
  5. Return outcome.

Complexity

  • ⏰ Time complexity:
    • addWord: O(L) as insertion is simple down the path;
    • search exact: O(L);
    • search pattern: O(N * L) as we may have to go through whole of trie, but if the trie is complete, then it can be O(a^L), where is alphabet size, which is 26 for this problem.
  • 🧺 Space complexity: O(N * L) for trie nodes; recursion stack O(L); auxiliary O(1) per frame (no substring allocations).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

class WordDictionary {
    private static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEndOfWord = false;
    }

    private final TrieNode root;

    public WordDictionary() {
        root = new TrieNode();
    }

    public void addWord(String word) {
        TrieNode curr = root;
        for (char c : word.toCharArray()) {
            if (curr.children[c - 'a'] == null) {
                curr.children[c - 'a'] = new TrieNode();
            }
            curr = curr.children[c - 'a'];
        }
        curr.isEndOfWord = true;
    }

    public boolean search(String word) {
        return searchInNode(word, 0, root);
    }

    private boolean searchInNode(String word, int index, TrieNode node) {
        if (node == null) {
            return false;
        }
        if (index == word.length()) {
            return node.isEndOfWord;
        }

        char c = word.charAt(index);

        if (c == '.') {
            for (TrieNode child : node.children) {
                if (searchInNode(word, index + 1, child)) {
                    return true;
                }
            }
            return false;
        } else {
            TrieNode child = node.children[c - 'a'];
            return searchInNode(word, index + 1, child);
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class TrieNode:
	def __init__(self):
		self.children: list[TrieNode | None] = [None] * 26
		self.is_end_of_word = False

class WordDictionary:
	def __init__(self):
		self.root = TrieNode()

	def addWord(self, word: str) -> None:
		curr = self.root
		for c in word:
			idx = ord(c) - ord('a')
			if curr.children[idx] is None:
				curr.children[idx] = TrieNode()
			curr = curr.children[idx]
		curr.is_end_of_word = True

	def search(self, pattern: str) -> bool:
		def searchInNode(node: TrieNode | None, i: int) -> bool:
			if node is None:
				return False
			if i == len(pattern):
				return node.is_end_of_word
			c = pattern[i]
			if c == '.':
				for child in node.children:
					if child and searchInNode(child, i + 1):
						return True
				return False
			idx = ord(c) - ord('a')
			return searchInNode(node.children[idx], i + 1)

		return searchInNode(self.root, 0)