Sponsored
Sponsored
This approach involves using a Trie data structure, which is highly efficient for dynamic prefix search operations. Each node of the Trie represents a character of a string. For the search operation, if the current character is a dot '.', then recursively search all possible nodes. This allows the Trie to handle strings with wildcard characters.
Time Complexity: O(n) for addWord and O(m^26) in the worst case for search where m is the length of the word.
Space Complexity: O(total_characters) for the trie structure.
1class TrieNode:
2 def __init__(self):
3 self.children = {}
4 self.is_end_of_word = False
5
6class WordDictionary:
7 def __init__(self):
8 self.root = TrieNode()
9
10 def addWord(self, word: str) -> None:
11 node = self.root
12 for char in word:
13 if char not in node.children:
14 node.children[char] = TrieNode()
15 node = node.children[char]
16 node.is_end_of_word = True
17
18 def search(self, word: str) -> bool:
19 def search_in_node(word, node):
20 for i, char in enumerate(word):
21 if char == '.':
22 for child in node.children.values():
23 if search_in_node(word[i + 1:], child):
24 return True
25 return False
26 else:
27 if char not in node.children:
28 return False
29 node = node.children[char]
30 return node.is_end_of_word
31 return search_in_node(word, self.root)The Python implementation initializes a Trie structure with a root node. addWord iterates through the characters of the word and constructs nodes if they do not exist. search checks each character. When it encounters a '.', it branches out recursively to all children nodes. This efficiently handles wildcard searches.
This approach uses a combination of a HashMap (Dictionary in some languages) to store words based on their lengths. The search checks the word's length first and retrieves potential matches. For wildcards, a Depth-First Search (DFS) explores possible character matches sequentially.
Time Complexity: O(m*n) for search, where m is the number of words of the same length and n is the length of the word.
Space Complexity: O(total_chars) for storing words in the HashMap.
1import java.util.*;
2
3class WordDictionary {
Tries, also known as prefix trees, are efficient for searching words by prefixes and can be adapted to handle wildcard characters. In this approach:
Time Complexity: O(n) for adding a word and average of O(n*m) for searching a word, where n is the length of the word and m is the branching factor of the trie. Space Complexity: O(n*m) for storing words in the trie.
In this approach, we utilize backtracking for the search operation. This approach is simpler in terms of implementation but may not be as efficient as using a Trie due to repetitive computations:
addWord function, simply add the word to the list.search function, iterate through each stored word, and use recursion to handle '.' in the search query, comparing matching paths or using any letter at wildcard positions.Time Complexity: O(m * n) for search, where m is the number of words and n is the average length of the longest word. Space Complexity: O(t * l) for the list, where t is the total words stored, and l is their average length.
The Java solution uses a HashMap to categorize words by their length, providing O(1) access to words of the same size during the search. The DFS-like isMatch function is straightforward, checking corresponding positions of candidate words and query words. It allows efficient handling of the '.' wildcard.
The Python code defines a WordDictionary class using a TrieNode class for node representation. The addWord function inserts a word into the trie. The search function handles '.' using a recursive DFS approach, allowing branching wherever a dot is encountered.
The Python solution implements WordDictionary using a list to store words. The addWord method appends words to the list, and search checks each word for matching pattern lengths and characters or wildcards using helper function.