Design Add and Search Words Data Structure

We need to design a data structure that supports adding new words and searching words, including words with wildcard characters. A trie would be an excellent fit for this problem, as it allows for efficient insertion and search of strings.

Here’s a step-by-step explanation of how to implement this data structure:

Initialize the Trie: The Trie structure contains a root node and possibly child nodes for each letter of the alphabet.
Add Word: To add a word, start from the root and follow the path corresponding to each letter in the word. If the corresponding child node doesn’t exist, create it. Mark the last node of the word as an end-of-word node.
Search Word: To search for a word, start from the root and follow the path corresponding to each letter in the word. If a wildcard character ‘.’ is encountered, search all child nodes recursively. If an end-of-word node is reached at the end of the word, return true.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class WordDictionary:

    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word: str) -> bool:
        return self.search_recursive(word, 0, self.root)

    def search_recursive(self, word: str, index: int, node: TrieNode) -> bool:
        if index == len(word):
            return node.is_end_of_word
        
        char = word[index]
        if char == '.':
            for child in node.children.values():
                if self.search_recursive(word, index + 1, child):
                    return True
            return False
        elif char in node.children:
            return self.search_recursive(word, index + 1, node.children[char])
        else:
            return False

Explanation of the code:

TrieNode class is used to represent each node in the trie.
addWord method is used to insert a word into the trie.
search method is used to search for a word in the trie. It calls a recursive function search_recursive that handles the search, including handling wildcard characters.

The time complexity for addWord is O(L), where L is the length of the word, and the time complexity for search can be up to O(26^L) in the worst case (when there are wildcards at every position). The space complexity is O(N), where N is the total number of characters in all the words in the trie.

Here is an implementation of the WordDictionary class in Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class TrieNode:
    def __init__(self):
        self.children = {}
        self.end = False

class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        node = self.root
        for c in word:
            if c not in node.children: 
                node.children[c] = TrieNode()
            node = node.children[c]
        node.end = True

    def search(self, word: str) -> bool:
        def dfs(j, root):
            node = root

            for i in range(j, len(word)):
                if word[i] == '.':
                    if not node.children:
                        return False
                    return any(dfs(i+1, child) for child in node.children.values())
                else:
                    if word[i] not in node.children:
                        return False
                    node = node.children[word[i]]

            return node.end

        return dfs(0, self.root)

The key ideas are:

Use a Trie to store all words
For search, do DFS traversal
Handle ‘.’ by recursing into all child nodes
Return true if reach end of word in Trie

This allows efficiently finding if words exist in Trie during search with wildcards.

How do we implement WordDictionary?
What datastructure can we use?
- Hashtable
- Trie - Is better in terms of performance

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
class TrieNode
    attr_accessor :end_of_word, :links
    
    def initialize()
        @links = {}
        @end_of_word = false
     end        
end

class WordDictionary

=begin
    Initialize your data structure here.
=end
    def initialize()
         @root = TrieNode.new
    end


=begin
    :type word: String
    :rtype: Void
=end
    def add_word(word)
        node = @root
        for i in (0..word.size - 1)
            letter = word[i]
            if !node.links.key?(letter)
                node.links[letter] = TrieNode.new
            end
            node = node.links[letter]
        end
        node.end_of_word = true
    end


=begin
    :type word: String
    :rtype: Boolean
=end
    
   def search(word)
       node = @root
       return search_wrapper(word, node)
    end
            
def search_wrapper(word, node)
  
  for i in (0..word.size - 1)
    letter = word[i]
    if !node.links.key?(letter)
      if letter == '.'
        letters = node.links.keys
        letters.each do |letter|
          child = node.links[letter]
          if search_wrapper(word[i+1..-1], child)
            return true 
          end
        end
      end
      return false
    else
      node = node.links[letter]
    end
  end

  return node.end_of_word      
end


end

# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary.new()
# obj.add_word(word)
# param_2 = obj.search(word)