Design Add and Search Words Data Structure
Design Add and Search Words Data Structure
Design a data structure to store words and efficiently support word addition and searching, including flexible matching.
Implement the WordDictionary class with the following methods:
- addWord(word): Adds the given word to the data structure, allowing it to be stored for future searches. This is useful for building a collection of words dynamically.
- search(word): Searches for a word in the data structure. The search supports both exact matches and partial matches using the . character as a wildcard. The . can represent any letter, making the search versatile for patterns or incomplete words.
This structure is particularly useful for applications like pattern matching or word suggestions.
Example 1:
Input:
["WordDictionary", "addWord", "day", "addWord", "bay", "addWord", "may", "search", "say", "search", "day", "search", ".ay", "search", "b.."]
Output:
[null, null, null, null, false, true, true, true]
["WordDictionary", "addWord", "day", "addWord", "bay", "addWord", "may", "search", "say", "search", "day", "search", ".ay", "search", "b.."]
Output:
[null, null, null, null, false, true, true, true]
Explanation:
- WordDictionary wordDictionary = new WordDictionary();
- wordDictionary.addWord(“day”);
- wordDictionary.addWord(“bay”);
- wordDictionary.addWord(“may”);
- wordDictionary.search(“say”); // return false
- wordDictionary.search(“day”); // return true
- wordDictionary.search(“.ay”); // return true
- wordDictionary.search(“b..”); // return true
Constraints:
- 1 <= word.length <= 20
- word in addWord consists of lowercase English letters.
- word in search consist of ‘.’ or lowercase English letters.
Design Add and Search Words Data Structure Solution
Recommendation for Time and Space Complexity – Aim for O(n) time per function call and O(t + n) space, where n is the word length and t is the number of nodes in the Trie.
Hints for solving problems
Hint 1 :
A brute force approach stores words in a list and searches through it, taking O(m * n) time. Consider a more efficient solution, like using a tree-like structure.
Hint 2 :
Use a Trie for efficient word insertion and search. For . (wildcard), recursively check all possible characters at that position.
Hint 3 :
While traversing the word:
- Match characters normally.
- For “.” explore all possible paths recursively.
- The complexity remains O((26^2) * n), as there are at most two . in a word.
There are mainly 2 approach to solve this problem-
- Brute Force Method
- Depth First Search(Trie) Method
1. Brute Force Method
Words are stored in a list, and each search checks all words by iterating through them, including handling wildcards (.) character by character. This leads to a time complexity of O(m * n), where m is the number of words and n is the word length.
- Time complexity: O(n) for addWord(), O(m∗n) for search().
- Space complexity: O(m*n)
where m is the number of words added and n is the length of the string.
Code
C++
Java
Python
JavaScript
C++
class WordDictionary {
public:
vector<string> store;
WordDictionary() {}
void addWord(string word) {
store.push_back(word);
}
bool search(string word) {
for (string w : store) {
if (w.length() != word.length()) continue;
int i = 0;
while (i < w.length()) {
if (w[i] == word[i] || word[i] == '.') {
i++;
} else {
break;
}
}
if (i == w.length()) {
return true;
}
}
return false;
}
};
Java
public class WordDictionary {
private List<String> store;
public WordDictionary() {
store = new ArrayList<>();
}
public void addWord(String word) {
store.add(word);
}
public boolean search(String word) {
for (String w : store) {
if (w.length() != word.length()) continue;
int i = 0;
while (i < w.length()) {
if (w.charAt(i) == word.charAt(i) ||
word.charAt(i) == '.') {
i++;
} else {
break;
}
}
if (i == w.length()) {
return true;
}
}
return false;
}
}
Python
class WordDictionary:
def __init__(self):
self.store = []
def addWord(self, word: str) -> None:
self.store.append(word)
def search(self, word: str) -> bool:
for w in self.store:
if len(w) != len(word):
continue
i = 0
while i < len(w):
if w[i] == word[i] or word[i] == '.':
i += 1
else:
break
if i == len(w):
return True
return False
JavaScript
class WordDictionary {
constructor() {
this.store = [];
}
/**
* @param {string} word
* @return {void}
*/
addWord(word) {
this.store.push(word);
}
/**
* @param {string} word
* @return {boolean}
*/
search(word) {
for (let w of this.store) {
if (w.length !== word.length) continue;
let i = 0;
while (i < w.length) {
if (w[i] === word[i] ||
word[i] === '.') {
i++;
} else {
break;
}
}
if (i === w.length) {
return true;
}
}
return false;
}
}
2. Depth First Search(Trie) Method
Words are stored in a trie, and searches are done using depth-first search (DFS). Wildcards (.) are handled by recursively checking all possible matches at each position, improving search efficiency to O(n) time complexity, where n is the word length.
- Time complexity: O(n) for addWord(), O(n) for search().
- Space complexity: O(t+n)
where n is the length of the string and t is the total number of TrieNodes created in the Trie.
Code
C++
Java
Python
JavaScript
C++
class TrieNode {
public:
vector<TrieNode*> children;
bool word;
TrieNode() : children(26, nullptr), word(false) {}
};
class WordDictionary {
public:
TrieNode* root;
WordDictionary() : root(new TrieNode()) {}
void addWord(string word) {
TrieNode* cur = root;
for (char c : word) {
if (cur->children[c - 'a'] == nullptr) {
cur->children[c - 'a'] = new TrieNode();
}
cur = cur->children[c - 'a'];
}
cur->word = true;
}
bool search(string word) {
return dfs(word, 0, root);
}
private:
bool dfs(string word, int j, TrieNode* root) {
TrieNode* cur = root;
for (int i = j; i < word.size(); i++) { char c = word[i]; if (c == '.') { for (TrieNode* child : cur->children) {
if (child != nullptr && dfs(word, i + 1, child)) {
return true;
}
}
return false;
} else {
if (cur->children[c - 'a'] == nullptr) {
return false;
}
cur = cur->children[c - 'a'];
}
}
return cur->word;
}
};
Java
public class TrieNode {
TrieNode[] children;
boolean word;
public TrieNode() {
children = new TrieNode[26];
word = false;
}
}
public class WordDictionary {
private TrieNode root;
public WordDictionary() {
root = new TrieNode();
}
public void addWord(String word) {
TrieNode cur = root;
for (char c : word.toCharArray()) {
if (cur.children[c - 'a'] == null) {
cur.children[c - 'a'] = new TrieNode();
}
cur = cur.children[c - 'a'];
}
cur.word = true;
}
public boolean search(String word) {
return dfs(word, 0, root);
}
private boolean dfs(String word, int j, TrieNode root) {
TrieNode cur = root;
for (int i = j; i < word.length(); i++) {
char c = word.charAt(i);
if (c == '.') {
for (TrieNode child : cur.children) {
if (child != null && dfs(word, i + 1, child)) {
return true;
}
}
return false;
} else {
if (cur.children[c - 'a'] == null) {
return false;
}
cur = cur.children[c - 'a'];
}
}
return cur.word;
}
}
Python
class TrieNode:
def __init__(self):
self.children = {}
self.word = 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.children:
cur.children[c] = TrieNode()
cur = cur.children[c]
cur.word = True
def search(self, word: str) -> bool:
def dfs(j, root):
cur = root
for i in range(j, len(word)):
c = word[i]
if c == ".":
for child in cur.children.values():
if dfs(i + 1, child):
return True
return False
else:
if c not in cur.children:
return False
cur = cur.children[c]
return cur.word
return dfs(0, self.root)
JavaScript
class TrieNode {
constructor() {
this.children = Array(26).fill(null);
this.word = false;
}
}
class WordDictionary {
constructor() {
this.root = new TrieNode();
}
/**
* @param {string} c
* @return {number}
*/
getIndex(c) {
return c.charCodeAt(0) - 'a'.charCodeAt(0);
}
/**
* @param {string} word
* @return {void}
*/
addWord(word) {
let cur = this.root;
for (const c of word) {
const idx = this.getIndex(c);
if (cur.children[idx] === null) {
cur.children[idx] = new TrieNode();
}
cur = cur.children[idx];
}
cur.word = true;
}
/**
* @param {string} word
* @return {boolean}
*/
search(word) {
return this.dfs(word, 0, this.root);
}
/**
* @param {string} word
* @param {number} j
* @param {TrieNode} root
* @return {boolean}
*/
dfs(word, j, root) {
let cur = root;
for (let i = j; i < word.length; i++) {
const c = word[i];
if (c === '.') {
for (const child of cur.children) {
if (child !== null &&
this.dfs(word, i + 1, child)) {
return true;
}
}
return false;
} else {
const idx = this.getIndex(c);
if (cur.children[idx] === null) {
return false;
}
cur = cur.children[idx];
}
}
return cur.word;
}
}
