Last updated on January 5th, 2025 at 01:07 am
Here, we see a Design Add and Search Words Data Structure LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Backtracking, Design, Trie
Companies
Level of Question
Medium
Design Add and Search Words Data Structure LeetCode Solution
Table of Contents
1. Problem Statement
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)Addswordto the data structure, it can be matched later.bool search(word)Returnstrueif there is any string in the data structure that matcheswordorfalseotherwise.wordmay contain dots'.'where dots can be matched with any letter.
Example:
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
2. Coding Pattern Used in Solution
The provided code implements a Trie (Prefix Tree) data structure, which is commonly used for problems involving string manipulation, such as word search, autocomplete, and dictionary operations.
3. Code Implementation in Different Languages
3.1 Design Add and Search Words Data Structure C++
class TrieNode {
public:
bool word;
TrieNode* children[26];
TrieNode() {
word = false;
memset(children, NULL, sizeof(children));
}
};
class WordDictionary {
public:
WordDictionary() {
}
void addWord(string word) {
TrieNode* node = root;
for (char c : word) {
if (!node -> children[c - 'a']) {
node -> children[c - 'a'] = new TrieNode();
}
node = node -> children[c - 'a'];
}
node -> word = true;
}
bool search(string word) {
return search(word.c_str(), root);
}
private:
TrieNode* root = new TrieNode();
bool search(const char* word, TrieNode* node) {
for (int i = 0; word[i] && node; i++) {
if (word[i] != '.') {
node = node -> children[word[i] - 'a'];
} else {
TrieNode* tmp = node;
for (int j = 0; j < 26; j++) {
node = tmp -> children[j];
if (search(word + i + 1, node)) {
return true;
}
}
}
}
return node && node -> word;
}
};
3.2 Design Add and Search Words Data Structure Java
class WordDictionary {
private WordDictionary[] children;
boolean isEndOfWord;
public WordDictionary() {
children = new WordDictionary[26];
isEndOfWord = false;
}
public void addWord(String word) {
WordDictionary curr = this;
for(char c: word.toCharArray()){
if(curr.children[c - 'a'] == null)
curr.children[c - 'a'] = new WordDictionary();
curr = curr.children[c - 'a'];
}
curr.isEndOfWord = true;
}
public boolean search(String word) {
WordDictionary curr = this;
for(int i = 0; i < word.length(); ++i){
char c = word.charAt(i);
if(c == '.'){
for(WordDictionary ch: curr.children)
if(ch != null && ch.search(word.substring(i+1))) return true;
return false;
}
if(curr.children[c - 'a'] == null) return false;
curr = curr.children[c - 'a'];
}
return curr != null && curr.isEndOfWord;
}
}
3.3 Design Add and Search Words Data Structure JavaScript
class Node{
constructor(){
this.keys = new Map();
this.end = false;
}
setEnd(){this.end = true;}
isEnd(){return this.end}
}
var WordDictionary = function() {
this.root = new Node();
};
WordDictionary.prototype.addWord = function(word) {
let node = this.root;
function rec(node, word){
if(word){
if(!node.keys.has(word[0]))
node.keys.set(word[0], new Node());
return rec(node.keys.get(word[0]), word.substr(1));
}
else node.setEnd();
}
rec(node, word)
return true;
};
WordDictionary.prototype.search = function(word) {
let node = this.root;
function rec(node, word){
if(!node) return false;
if(word){
if(word[0]==='.'){
let out = false;
for(let val of node.keys.keys()){
out = out || rec(node.keys.get(val), word.substr(1));
}
return out;
}
else if(node.keys.has(word[0])){
return rec(node.keys.get(word[0]), word.substr(1));
}
else{ return false}
}
else return node.isEnd();
}
return rec(node, word);
};
3.4 Design Add and Search Words Data Structure Python
class WordDictionary(object):
def __init__(self):
self.children = [None]*26
self.isEndOfWord = False
def addWord(self, word):
curr = self
for c in word:
if curr.children[ord(c) - ord('a')] == None:
curr.children[ord(c) - ord('a')] = WordDictionary()
curr = curr.children[ord(c) - ord('a')]
curr.isEndOfWord = True;
def search(self, word):
curr = self
for i in range(len(word)):
c = word[i]
if c == '.':
for ch in curr.children:
if ch != None and ch.search(word[i+1:]): return True
return False
if curr.children[ord(c) - ord('a')] == None: return False
curr = curr.children[ord(c) - ord('a')]
return curr != None and curr.isEndOfWord
4. Time and Space Complexity
| addWord | O(L) | O(L) |
| search | O(26L) in the worst case (wildcard search with . at every position) | O(L) for the recursion stack during wildcard search |