Solution For Design Add And Search Words Data Structure

Design Add And Search Words Data Structure problem on LeetCode can be solved using Trie data structure. The problem statement requires us to design a data structure that supports adding and searching for words. The search operation can also have wildcard characters represented by a ‘.’, which can match any character.

Let’s start by understanding Trie data structure. Trie or prefix tree is a tree-based data structure used to store a collection of strings efficiently. Each node in the Trie represents a prefix of a word. The root represents an empty string, and each edge is labeled with a character. The child nodes represent prefixes formed by appending characters to the prefix of the parent node.

The solution involves building a Trie tree of words. Since we need to support wildcard search, we add an extra condition to the Trie node, which checks if the node has a wildcard character (‘.’) as a child.

The data structure will have two main operations:

1. addWord(word): This operation will add a new word to the Trie tree. We iterate over each character of the word and add each character as a new node in the Trie. We mark the last node of the word as an end of word node.
2. search(word): This operation will search for the given word in the Trie tree. We iterate over each character of the word and check if the character exists in the current node’s children. If the character exists, we move to that node and continue the search. If the character is ‘.’, we search all the children of the current node and move to the next character.

The search operation also needs to check for wildcard characters. To support this, we explore all the children of the current node for wildcard characters recursively until we find a match or reach the end of the Trie.

Here is the Python implementation of the data structure:

“`
class TrieNode:
def init(self):
self.children = {}
self.isEndOfWord = False
self.isWildcard = False

class WordDictionary:

def __init__(self):
    """
    Initialize your data structure here.
    """
    self.root = TrieNode()

def addWord(self, word: str) -> None:
    """
    Adds a word into the data structure.
    """
    node = self.root
    for char in word:
        if char not in node.children:
            node.children[char] = TrieNode()
        node = node.children[char]
    node.isEndOfWord = True

def search(self, word: str) -> bool:
    """
    Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
    """
    return self.searchRecursive(word, self.root)

def searchRecursive(self, word: str, node: TrieNode) -> bool:
    if not word:
        return node.isEndOfWord
    char = word[0]
    if char != ".":
        if char not in node.children:
            return False
        return self.searchRecursive(word[1:], node.children[char])
    else:
        for child in node.children.values():
            if self.searchRecursive(word[1:], child):
                return True
        return False

“`

Time Complexity:

Add O(m), where m is the length of the word being added.

Search O(n26^m), where n is the number of words in the Trie and m is the length of the searched word. The complexity is at most n26^m, since for each of the n words in the Trie, we can potentially recurse down all the children nodes (26 branching factors at each node), representing all possible combinations of the search word with wildcard characters.

Space Complexity:

O(nm26), where n is the number of words, m is the average length of the word, and 26 is the size of the English alphabet. The space complexity comes from storing the Trie nodes. Note that this can be optimized by compressing the Trie using techniques like suffix tree.

Step by Step Implementation For Design Add And Search Words Data Structure

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

class WordDictionary {
    
    // Add a word into the data structure.
    public void addWord(String word) {
        
    }

    // 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) {
        
    }
}

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary = new WordDictionary();
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");

class WordDictionary:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.word_list = []
        

    def addWord(self, word: str) -> None:
        """
        Adds a word into the data structure.
        """
        self.word_list.append(word)
        

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
        """
        for w in self.word_list:
            if len(w) != len(word):
                continue
            for i in range(len(w)):
                if w[i] == word[i] or word[i] == '.':
                    continue
                else:
                    break
            else:
                return True
        return False

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

// Implement the WordDictionary class:

// WordDictionary() Initializes the object.
// void addWord(word) Adds word into the data structure, it can be matched later.
// bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be replaced with any letter.
 
// Example:

// Input
// ["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
// [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
// Output
// [null,null,null,null,false,true,true,true]

// Explanation
// WordDictionary wordDictionary = new WordDictionary();
// wordDictionary.addWord("bad");
// wordDictionary.addWord("dad");
// wordDictionary.addWord("mad");
// wordDictionary.search("pad"); // return False
// wordDictionary.search("bad"); // return True
// wordDictionary.search(".ad"); // return True
// wordDictionary.search("b.."); // return True

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)
search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

Example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search("..d") -> true
Note:
You may assume that all words are consist of lowercase letters a-z.

public class WordDictionary {
    
    /** Initialize your data structure here. */
    public WordDictionary() {
        
    }
    
    /** Adds a word into the data structure. */
    public void AddWord(string word) {
        
    }
    
    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    public bool Search(string word) {
        
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.AddWord(word);
 * bool param_2 = obj.Search(word);
 */