Design Add and Search Words Data Structure

struct TrieNode {
    unordered_map<char, TrieNode*> next;
    bool isEndOfWord = false;
};

class WordDictionary {
    TrieNode* root;

public:
    WordDictionary() { root = new TrieNode(); }

    void addWord(string word) {
        TrieNode* current = root;

        for (char ch : word) {
            if (!current->next.count(ch)) {
                current->next[ch] = new TrieNode();
            }
            current = current->next[ch];
        }
        current->isEndOfWord = true;
    }

    bool deepSearch(string word, TrieNode* currentNode) {
        for (int i = 0; i < word.size(); ++i) {
            char ch = word[i];
            if (!currentNode->next.count(ch)) {
                if (ch == '.') {
                    for (auto pair : currentNode->next) {
                        TrieNode* childNode = pair.second;
                        if (deepSearch(word.substr(i + 1), childNode)) {
                            return true;
                        }
                    }
                }
                return false;
            } else {
                currentNode = currentNode->next[ch];
            }
        }
        return currentNode->isEndOfWord;
    }

    bool search(string word) { return deepSearch(word, root); }
};

Implement a data structure called WordDictionary that supports adding and searching words using C++. This data structure particularly supports searching of words with specific wildcards denoted by the character '.' which can match any character.

• Implement the WordDictionary using a Trie (prefix tree) to store words.
• Create a structure TrieNode which consists of:
  • A hashmap to hold child nodes.
  • A boolean to flag the end of a word within the Trie.
• Initialize the WordDictionary with a root node that represents an empty Trie.

Adding a Word

1. Start from the root.
2. Iterate over each character of the word to be added.
3. Check if the current character exists in the children of the current TrieNode:
   • If not present, create a new TrieNode and link it.
   • Move to the next node.
4. After inserting all characters of the word, mark the last node as the end of the word.

Searching for a Word

1. Use a helper function deepSearch which is recursively called to evaluate the word against the Trie structure.
2. For each character in the word:
   • If the character is '.', recursively search in all possible child paths.
   • If the character is not found in the current node and is not '.', return false.
   • If a match is found, move to the next character.
3. Return true if the end of the string corresponds to isEndOfWord flag of a TrieNode.

This structure efficiently manages dynamic dictionary operations and wildcard-supported searches.

class TrieNode {
    Map<Character, TrieNode> childrenMap = new HashMap<>();
    boolean endOfWord = false;

    public TrieNode() {}
}

class WordDictionary {
    TrieNode root;

    /** Initialize your data structure here. */
    public WordDictionary() {
        root = new TrieNode();
    }

    /** Adds a word into the data structure. */
    public void addWord(String word) {
        TrieNode currentNode = root;

        for (char ch : word.toCharArray()) {
            if (!currentNode.childrenMap.containsKey(ch)) {
                currentNode.childrenMap.put(ch, new TrieNode());
            }
            currentNode = currentNode.childrenMap.get(ch);
        }
        currentNode.endOfWord = true;
    }

    /** Returns if the word is in the node. */
    public boolean searchInNode(String word, TrieNode node) {
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            if (!node.childrenMap.containsKey(ch)) {
                if (ch == '.') {
                    for (char key : node.childrenMap.keySet()) {
                        TrieNode childNode = node.childrenMap.get(key);
                        if (searchInNode(word.substring(i + 1), childNode)) {
                            return true;
                        }
                    }
                }
                return false;
            } else {
                node = node.childrenMap.get(ch);
            }
        }
        return node.endOfWord;
    }

    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    public boolean search(String word) {
        return searchInNode(word, root);
    }
}

The provided Java code demonstrates the construction and operation of a specialized data structure using a Trie (often called a prefix tree) to store and search for words with efficient time complexity. The core functionalities of this structure are encapsulated in two main classes: TrieNode and WordDictionary.

• TrieNode class:

  • It contains a HashMap childrenMap to map each character to its subsequent TrieNode.
  • It also has a boolean endOfWord to denote the end of a word.

• WordDictionary class:

  1. Initializes an empty root node of TrieNode.
  2. addWord(String word): Implements the addition of a word to the dictionary. It traverses each character of the word, checks its existence in the current node's childrenMap, and if not present, creates a new TrieNode. The node corresponding to the last character is marked with endOfWord = true to signify the completion of the word.
  3. search(String word): Facilitates the search for a word, including support for wildcard characters represented by '.'. It invokes searchInNode(String word, TrieNode node) which is recursive.
  4. searchInNode(String word, TrieNode node): Recursively checks each character of the word in the trie. If a character is '.', it iterates over all possible child nodes. For a typical character, it moves to the corresponding child node if exists; otherwise, the search returns false. If the end of the word is reached within the Trie and endOfWord is true, it confirms the word's existence in the dictionary.

This code effectively addresses the challenges of designing a data structure that supports both the efficient addition of words and their flexible search, including the use of wildcards, thereby demonstrating a fundamental application of Trie data structures for tasks involving pattern matching and word lookups.

class Lexicon:

    def __init__(self):
        self.root = {}

    def insertWord(self, word: str) -> None:
        current = self.root
        for letter in word:
            if letter not in current:
                current[letter] = {}
            current = current[letter]
        current["*"] = True

    def find(self, word: str) -> bool:

        def dfs_search(part, node) -> bool:
            for index, char in enumerate(part):
                if char not in node:
                    if char == '.':
                        for k in node:
                            if k != '*' and dfs_search(part[index + 1:], node[k]):
                                return True
                    return False
                else:
                    node = node[char]
            return '*' in node

        return dfs_search(word, self.root)

The solution provided implements a data structure that allows adding and searching words with support for wildcard characters. The implementation is in Python and employs a Trie (prefix tree) structure for efficient storage and search. Here's a summary of how the code works:

• Initialization (__init__ method):

  • Start by creating a root dictionary. This dictionary serves as the starting point of the Trie.

• Inserting a word (insertWord method):

  • Traverse the structure character by character from the root. If a character does not exist at any node, create a new dictionary at that node.
  • Once the end of the word is reached, mark this end in the Trie with a special character "*" set to True to indicate the end of a valid word.

• Searching a word (find method):

  • Implement a recursive function dfs_search to delve into the Trie. It handles two scenarios:
    • For regular characters, follow the path directly in the Trie.
    • For the wildcard character '.', iterate through all possible nodes at the current Trie path. Recursively search from the next part of the word.
  • The base case for the recursion checks if the end of the part is matched in the Trie through the presence of the "*" in the current node.

The design supports use of wildcard elements represented by '.', which makes it versatile for matching patterns within added words, not just exact word matches. This data structure is efficient for operations like search suggestions and spell-checkers where pattern matching is crucial.