algoadvance

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

Clarifying Questions

  1. Q: Any restrictions on the length of the words? A: No specific restrictions mentioned in the problem.

  2. Q: Will the characters always be lowercase English letters? A: Yes, that’s the assumption based on typical constraints of the problem.

  3. Q: Can word contain both normal characters and dots in any position? A: Yes, word can be composed of lowercase English letters in addition to the dot (.) wildcard character.

Strategy

  1. Trie Data Structure:
    • We’ll use a Trie (Prefix Tree) where each node represents a letter.
    • Each Trie node will have a pointer to its children (26 possible children for each letter of the alphabet).
  2. addWord Method:
    • Traverse the Trie according to the characters in the input word.
    • If the character’s node does not exist, create a new node.
    • Mark the end of the word in the Trie.
  3. search Method:
    • To handle the . wildcard, we need a recursive search function.
    • If the current character is ., recursively search all possible paths for the children nodes.
    • For normal characters, follow the path dictated by the Trie structure.
    • If we reach the end of the word, check if it’s marked as an end of a word in the Trie.

Code

class TrieNode:
    def __init__(self):
        self.children = {}
        self.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.end_of_word = True

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

    def _search_recursive(self, node: TrieNode, word: str, index: int) -> bool:
        if index == len(word):
            return node.end_of_word

        if word[index] == '.':
            for child in node.children.values():
                if self._search_recursive(child, word, index + 1):
                    return True
        else:
            char = word[index]
            if char in node.children:
                return self._search_recursive(node.children[char], word, index + 1)
        
        return False

Time Complexity

  1. addWord(word):
    • Time complexity: (O(n)), where (n) is the length of the word. Each character is processed once.
  2. search(word):
    • Worst-case Time complexity: (O(m \cdot n)), where (m) is the length of the word and (n) is the number of characters in the Trie (for the worst case where all nodes are explored due to the . wildcard).
    • Best-case Time complexity: (O(m)), where (m) is the length of the word (when no wildcards are present and all nodes match directly).

This solution efficiently handles the requirements using a Trie along with recursive search to cater to the . wildcard.

Try our interview co-pilot at AlgoAdvance.com