design_add_and_search_words_data_structure

View Source

 1from collections import defaultdict
 2
 3
 4# @leet start
 5class Node:
 6    def __init__(self):
 7        self.children = defaultdict(Node)
 8        self.is_word = False
 9
10
11class WordDictionary:
12    """
13    This problem asks us to design a trie that can handle matches with wildcards.
14    This question is basically asking us to design the kleene star.
15
16    So, as in a normal tree, addWord is the same - we have a root node, and
17    for every character in the list, we keep adding it to the current pointer's
18    children unless it already exists, then we do nothing (to not overwrite our
19    progress) until we can't anymore then we set that character's is word to true.
20
21    For the search function, we need to implement searching with wildcards.
22    To do that, if we encounter a '.', we match any one character, so we increment
23    our current index by one and then pass in all of the children of the current node
24    to the search_wildcard function. If any of them match, we have a match.
25
26    Otherwise the function works as usual. We pass in the current pointer to the function
27    if needed.
28    """
29
30    def __init__(self):
31        self.root = Node()
32
33    def addWord(self, word: str) -> None:
34        curr = self.root
35        for c in word:
36            if c not in curr.children:
37                curr.children[c] = Node()
38            curr = curr.children[c]
39
40        curr.is_word = True
41
42    def search(self, word: str) -> bool:
43        def search_wildcard(word, curr):
44            for i, c in enumerate(word):
45                if c == ".":
46                    return any(
47                        search_wildcard(word[i + 1 :], potential_match)
48                        for potential_match in curr.children.values()
49                    )
50                if c not in curr.children:
51                    return False
52                curr = curr.children[c]
53            return curr.is_word
54
55        return search_wildcard(word, self.root)
56
57
58def test():
59    assert 2 + 2 == 4

class Node: View Source

6class Node:
7    def __init__(self):
8        self.children = defaultdict(Node)
9        self.is_word = False

children

is_word

class WordDictionary: View Source

12class WordDictionary:
13    """
14    This problem asks us to design a trie that can handle matches with wildcards.
15    This question is basically asking us to design the kleene star.
16
17    So, as in a normal tree, addWord is the same - we have a root node, and
18    for every character in the list, we keep adding it to the current pointer's
19    children unless it already exists, then we do nothing (to not overwrite our
20    progress) until we can't anymore then we set that character's is word to true.
21
22    For the search function, we need to implement searching with wildcards.
23    To do that, if we encounter a '.', we match any one character, so we increment
24    our current index by one and then pass in all of the children of the current node
25    to the search_wildcard function. If any of them match, we have a match.
26
27    Otherwise the function works as usual. We pass in the current pointer to the function
28    if needed.
29    """
30
31    def __init__(self):
32        self.root = Node()
33
34    def addWord(self, word: str) -> None:
35        curr = self.root
36        for c in word:
37            if c not in curr.children:
38                curr.children[c] = Node()
39            curr = curr.children[c]
40
41        curr.is_word = True
42
43    def search(self, word: str) -> bool:
44        def search_wildcard(word, curr):
45            for i, c in enumerate(word):
46                if c == ".":
47                    return any(
48                        search_wildcard(word[i + 1 :], potential_match)
49                        for potential_match in curr.children.values()
50                    )
51                if c not in curr.children:
52                    return False
53                curr = curr.children[c]
54            return curr.is_word
55
56        return search_wildcard(word, self.root)

This problem asks us to design a trie that can handle matches with wildcards. This question is basically asking us to design the kleene star.

So, as in a normal tree, addWord is the same - we have a root node, and for every character in the list, we keep adding it to the current pointer's children unless it already exists, then we do nothing (to not overwrite our progress) until we can't anymore then we set that character's is word to true.

For the search function, we need to implement searching with wildcards. To do that, if we encounter a '.', we match any one character, so we increment our current index by one and then pass in all of the children of the current node to the search_wildcard function. If any of them match, we have a match.

Otherwise the function works as usual. We pass in the current pointer to the function if needed.

root

def addWord(self, word: str) -> None: View Source

34    def addWord(self, word: str) -> None:
35        curr = self.root
36        for c in word:
37            if c not in curr.children:
38                curr.children[c] = Node()
39            curr = curr.children[c]
40
41        curr.is_word = True

def search(self, word: str) -> bool: View Source

43    def search(self, word: str) -> bool:
44        def search_wildcard(word, curr):
45            for i, c in enumerate(word):
46                if c == ".":
47                    return any(
48                        search_wildcard(word[i + 1 :], potential_match)
49                        for potential_match in curr.children.values()
50                    )
51                if c not in curr.children:
52                    return False
53                curr = curr.children[c]
54            return curr.is_word
55
56        return search_wildcard(word, self.root)

def test(): View Source

59def test():
60    assert 2 + 2 == 4