211. Design Add and Search Words Data Structure
DFS, Design, Trie, String, Review ·Problem Statement
link: https://leetcode.com/problems/design-add-and-search-words-data-structure/ https://leetcode.cn/problems/design-add-and-search-words-data-structure/
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.
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]
Solution Approach
The solution involves implementing a data structure called WordDictionary that allows adding words and searching for words with support for wildcard characters represented by ‘.’.
Algorithm
- Initialize the WordDictionary with an empty trie data structure.
- For adding a word, traverse the trie character by character and create new nodes as needed. Mark the end of the word with a ‘#’ symbol.
- For searching a word, use a depth-first search (DFS) function that explores the trie, character by character. If a ‘.’ is encountered in the word, recursively explore all possible child nodes. Return true if a matching word is found or false if not.
- Return the result of the search operation, indicating whether a word with the given pattern exists in the WordDictionary.
Implement
class WordDictionary:
def __init__(self):
self.trie = {}
def addWord(self, word: str) -> None:
cur = self.trie
for c in word:
if c not in cur:
cur[c] = {}
cur = cur[c]
cur['#'] = True
def search(self, word: str) -> bool:
return self.dfs(self.trie, word, 0)
def dfs(self, node, word, i):
if i == len(word):
return '#' in node
if word[i] == '.':
for child in node:
if child != '#' and self.dfs(node[child], word, i + 1):
return True
return False
if word[i] not in node:
return False
return self.dfs(node[word[i]], word, i + 1)