Design Add and Search Words Data Structure

 

1. Clarify the problem: Before diving into solving the problem, let's clarify the requirements:

  • We need to design a data structure to store words and perform two operations: addWord and search.
  • The addWord operation adds a word to the data structure.
  • The search operation searches for a word in the data structure. The word can contain letters or a dot character '.' that can match any letter.
  • The search operation should return true if the word exists in the data structure, and false otherwise.

2. Analyze the problem: To solve this problem, we can use a trie data structure, which is a tree-like data structure commonly used for efficient string matching and retrieval.

3. Design an algorithm: Here is the algorithm to design the data structure and implement the operations:

  1. Define a class called WordDictionary to represent the data structure.
  2. Define a class called TrieNode to represent a node in the trie data structure. Each node will have a character value, a flag indicating whether it represents the end of a word, and a dictionary to store its child nodes.
  3. In the WordDictionary class, implement the addWord operation:
    • Start from the root of the trie.
    • For each character in the word, check if there is a child node corresponding to that character. If not, create a new node and add it as a child.
    • Move to the child node and repeat the process for the next character.
    • After processing all characters, mark the last node as the end of a word.
  4. In the WordDictionary class, implement the search operation:
    • Start from the root of the trie.
    • For each character in the word:
      • If the character is a dot ('.'), recursively search in all child nodes of the current node.
      • If there is a child node corresponding to the character, move to that node and continue.
      • If there is no child node corresponding to the character or dot, return false.
    • After processing all characters, check if the last node represents the end of a word. If so, return true; otherwise, return false.

4. Explain your approach: The approach involves designing a trie data structure to store the words. Each node in the trie represents a character, and the edges between nodes represent the transitions between characters. We use a flag in each node to indicate whether it represents the end of a word. For the search operation, we traverse the trie based on the characters in the search word. If we encounter a dot ('.'), we recursively search in all child nodes. If we find a character that does not match or a missing child node, we return false. If we reach the end of the search word and the last node represents the end of a word, we return true.

5. Write clean and readable code:

python
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word_end = False


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

    def addWord(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_word_end = True

    def search(self, word):
        return self.searchRecursive(self.root, word)

    def searchRecursive(self, node, word):
        if not word:
            return node.is_word_end

        char = word[0]
        if char != '.':
            if char not in node.children:
                return False
            return self.searchRecursive(node.children[char], word[1:])
        else:
            for child in node.children.values():
                if self.searchRecursive(child, word[1:]):
                    return True
            return False

6. Test your code:

python
# Create a WordDictionary object
wordDictionary = WordDictionary()

# Test the addWord operation
wordDictionary.addWord("bad")
wordDictionary.addWord("dad")
wordDictionary.addWord("mad")

# Test the search operation
print(wordDictionary.search("pad"))  # Expected output: False
print(wordDictionary.search("bad"))  # Expected output: True
print(wordDictionary.search(".ad"))  # Expected output: True
print(wordDictionary.search("b.."))  # Expected output: True

# Add more test cases to validate the solution

7. Optimize if necessary: The provided solution is already efficient with a time complexity of O(M), where M is the length of the word being searched. The space complexity is O(N), where N is the total number of characters in all added words.

8. Handle error cases: The code assumes that the input words are valid strings containing only lowercase letters. If the input is empty or contains invalid characters, the behavior of the code is undefined.

9. Discuss complexity analysis: The time complexity of the addWord operation is O(L), where L is the length of the word being added. The time complexity of the search operation is O(M), where M is the length of the word being searched. The space complexity is O(N), where N is the total number of characters in all added words. The solution has an optimal time and space complexity given the problem requirements.

Next Post Previous Post