Add and Search Word
Solve this Problemwords to insert and a single pattern to search for, decide whether any inserted word matches it — where the pattern may contain '.', a wildcard that matches any single letter in that position. A pattern with no dots at all is just an ordinary exact-word lookup.
An ordinary trie walk follows exactly one child per character. A wildcard breaks that: at a '.', there's no single "next node" to commit to, so the search has to try every existing child and recurse into each — backtracking out of any branch that doesn't eventually pan out, and returning true the instant one does. Positions without a dot are still cheap, single-child steps; it's only the wildcards that fan the search out.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ words.length ≤ 1000 - ◆
1 ≤ words[i].length ≤ 25 - ◆
0 ≤ pattern.length ≤ 25 - ◆
words[i] consists of lowercase English letters only - ◆
pattern consists of lowercase English letters and the wildcard '.'
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Compare Against Each Word
BruteSkip building anything — just line the pattern up against every inserted word of the same length and compare character by character, treating a '.' in the pattern as an automatic match for whatever letter is there. The moment one word matches every position, return true. n words of length up to m each means up to O(n · m) work, redone from scratch for every search.
O(n · m)O(1)1class Solution {
2 public boolean wordDictionarySearch(String[] words, String pattern) {
3 for (String word : words) {
4 if (word.length() != pattern.length()) continue;
5 boolean match = true;
6 for (int i = 0; i < word.length(); i++) {
7 char p = pattern.charAt(i);
8 if (p != '.' && p != word.charAt(i)) {
9 match = false;
10 break;
11 }
12 }
13 if (match) return true;
14 }
15 return false;
16 }
17}Optimal — Trie with Backtracking DFS
OptimalInsert every word into a trie, same as ever. Searching is where it gets interesting: walk the pattern one character at a time, but when a '.' shows up, there's no single child to follow — try every one of the up to 26 children and recurse, backtracking the moment a branch dead-ends. An ordinary letter still costs O(1) per step, so a pattern with k wildcards costs at most O(26ᵏ) in the worst case, collapsing back to O(m) whenever there are no dots at all.
O(N + 26ᵏ)O(N)1class Solution {
2 static class TrieNode {
3 TrieNode[] children = new TrieNode[26];
4 boolean isEnd = false;
5 }
6
7 private boolean dfs(TrieNode node, String pattern, int pos) {
8 if (pos == pattern.length()) return node.isEnd;
9 char c = pattern.charAt(pos);
10 if (c == '.') {
11 for (TrieNode child : node.children) {
12 if (child != null && dfs(child, pattern, pos + 1)) return true;
13 }
14 return false;
15 }
16 int idx = c - 'a';
17 if (node.children[idx] == null) return false;
18 return dfs(node.children[idx], pattern, pos + 1);
19 }
20
21 public boolean wordDictionarySearch(String[] words, String pattern) {
22 TrieNode root = new TrieNode();
23 for (String word : words) {
24 TrieNode node = root;
25 for (char c : word.toCharArray()) {
26 int idx = c - 'a';
27 if (node.children[idx] == null) {
28 node.children[idx] = new TrieNode();
29 }
30 node = node.children[idx];
31 }
32 node.isEnd = true;
33 }
34 return dfs(root, pattern, 0);
35 }
36}