Design Add and Search Words Data Structure
Design Add and Search Words Data Structure is a medium tries problem solved with the basics pattern.
The best approach, optimal (trie with dfs on dots), runs in add O(L), search O(26^d · L) time and O(total characters · 26) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (list of words) up.
Problem
Design a WordDictionary class that stores words and answers lookup queries in which some letters may be unknown.
WordDictionary()creates an empty dictionary.addWord(word)storesword.search(word)returnstrueif some stored word matcheswordexactly, where every.inwordmay stand for any single letter. Otherwise it returnsfalse.
A query matches only a whole stored word of the same length; matching a prefix is not enough.
Examples
Example 1
- Input
addWord("lamp"), addWord("limp"), addWord("lam"), search("l.mp"), search("lam"), search("la"), search("..m")- Output
true, true, false, true- Why
- "l.mp" fits both "lamp" and "limp"; "la" is only a prefix, not a stored word; "..m" matches "lam".
Example 2
- Input
addWord("go"), search("."), search("g."), search("..o")- Output
false, true, false- Why
- A dot stands for exactly one letter, so the length must match too.
Constraints
1 <= word.length <= 25- Words passed to
addWordcontain only lowercase English letters. - Words passed to
searchcontain lowercase letters and.; at most 2 dots per query. - At most
10^4calls in total toaddWordandsearch.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (list of words) | add O(1), search O(N · L) | O(N · L) |
| Optimal (trie with DFS on dots) | add O(L), search O(26^d · L) | O(total characters · 26) |
1Brute force (list of words)
add O(1), search O(N · L)A search may compare against all N stored words, L characters each.O(N · L)Every stored character is kept.Keep every added word in a list. For a search, compare the query with each stored word of the same length, letting . match anything.
- addWord appends to the list.
- search loops over the list; skip words of another length; compare character by character, treating '.' as a match.
class WordDictionary {
private final List<String> words = new ArrayList<>();
public void addWord(String word) {
words.add(word);
}
public boolean search(String word) {
for (String w : words) {
if (w.length() != word.length()) continue;
boolean ok = true;
for (int i = 0; i < w.length() && ok; i++)
if (word.charAt(i) != '.' && word.charAt(i) != w.charAt(i)) ok = false;
if (ok) return true;
}
return false;
}
}class WordDictionary:
def __init__(self):
self.words = []
def addWord(self, word: str) -> None:
self.words.append(word)
def search(self, word: str) -> bool:
for w in self.words:
if len(w) != len(word):
continue
if all(c == '.' or c == x for c, x in zip(word, w)):
return True
return Falseclass WordDictionary {
vector<string> words;
public:
void addWord(string word) {
words.push_back(word);
}
bool search(string word) {
for (const string& w : words) {
if (w.size() != word.size()) continue;
bool ok = true;
for (size_t i = 0; i < w.size() && ok; i++)
if (word[i] != '.' && word[i] != w[i]) ok = false;
if (ok) return true;
}
return false;
}
};class WordDictionary {
constructor() {
this.words = [];
}
addWord(word) {
this.words.push(word);
}
search(word) {
for (const w of this.words) {
if (w.length !== word.length) continue;
let ok = true;
for (let i = 0; i < w.length && ok; i++)
if (word[i] !== '.' && word[i] !== w[i]) ok = false;
if (ok) return true;
}
return false;
}
}2Optimal (trie with DFS on dots)
add O(L), search O(26^d · L)Each of the at most d = 2 dots can branch 26 ways; letters follow a single path.O(total characters · 26)One trie node per distinct prefix, each with 26 child slots.Insert each word into a trie and mark the node where it ends. A search walks the trie: a letter moves to that one child, while a dot branches into every existing child. Shared prefixes are stored once, and a search only visits paths that exist.
- Node: children[26] and an end flag.
- addWord: walk/create children for each letter, set end = true at the last node.
- search(i, node): if i == length return node.end; if word[i] is '.', return true if any child succeeds; else follow that child if it exists.
class WordDictionary {
private static class Node {
Node[] next = new Node[26];
boolean end;
}
private final Node root = new Node();
public void addWord(String word) {
Node cur = root;
for (char c : word.toCharArray()) {
int k = c - 'a';
if (cur.next[k] == null) cur.next[k] = new Node();
cur = cur.next[k];
}
cur.end = true;
}
public boolean search(String word) {
return dfs(word, 0, root);
}
private boolean dfs(String word, int i, Node node) {
if (i == word.length()) return node.end;
char c = word.charAt(i);
if (c == '.') {
for (Node child : node.next)
if (child != null && dfs(word, i + 1, child)) return true;
return false;
}
Node child = node.next[c - 'a'];
return child != null && dfs(word, i + 1, child);
}
}class TrieNode:
def __init__(self):
self.next = {}
self.end = False
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(self, word: str) -> None:
cur = self.root
for c in word:
if c not in cur.next:
cur.next[c] = TrieNode()
cur = cur.next[c]
cur.end = True
def search(self, word: str) -> bool:
def dfs(i: int, node: TrieNode) -> bool:
if i == len(word):
return node.end
c = word[i]
if c == '.':
return any(dfs(i + 1, child) for child in node.next.values())
child = node.next.get(c)
return child is not None and dfs(i + 1, child)
return dfs(0, self.root)class WordDictionary {
struct Node {
Node* next[26] = {};
bool end = false;
};
Node* root = new Node();
bool dfs(const string& word, int i, Node* node) {
if (i == (int)word.size()) return node->end;
char c = word[i];
if (c == '.') {
for (Node* child : node->next)
if (child && dfs(word, i + 1, child)) return true;
return false;
}
Node* child = node->next[c - 'a'];
return child && dfs(word, i + 1, child);
}
public:
void addWord(string word) {
Node* cur = root;
for (char c : word) {
int k = c - 'a';
if (!cur->next[k]) cur->next[k] = new Node();
cur = cur->next[k];
}
cur->end = true;
}
bool search(string word) {
return dfs(word, 0, root);
}
};class WordDictionary {
constructor() {
this.root = { next: {}, end: false };
}
addWord(word) {
let cur = this.root;
for (const c of word) {
if (!cur.next[c]) cur.next[c] = { next: {}, end: false };
cur = cur.next[c];
}
cur.end = true;
}
search(word) {
const dfs = (i, node) => {
if (i === word.length) return node.end;
const c = word[i];
if (c === '.') {
for (const child of Object.values(node.next))
if (dfs(i + 1, child)) return true;
return false;
}
const child = node.next[c];
return child !== undefined && dfs(i + 1, child);
};
return dfs(0, this.root);
}
}Edge cases to test
- Searching before anything is added
- A query that is a prefix of a stored word (must be false)
- A query made only of dots
- Adding the same word twice
Hints
Hint 1
Store the words in a trie so that every prefix is shared.
Hint 2
A letter follows one child; a dot has to try every child of the current node.
FAQ
What is the best time complexity for Design Add and Search Words Data Structure?
Optimal (trie with DFS on dots) runs in add O(L), search O(26^d · L) time and O(total characters · 26) extra space. Each of the at most d = 2 dots can branch 26 ways; letters follow a single path.
Which pattern does Design Add and Search Words Data Structure use?
It is a tries problem that uses the basics pattern. Other problems with the same pattern: Implement Trie (Prefix Tree), Implement Trie ll, Design In-Memory File System.
Is there a brute force solution for Design Add and Search Words Data Structure?
Yes. Brute force (list of words) takes add O(1), search O(N · L) time and O(N · L) space. Keep every added word in a list.
Which edge cases should I test for Design Add and Search Words Data Structure?
Searching before anything is added; A query that is a prefix of a stored word (must be false); A query made only of dots; Adding the same word twice.