LeetCode_Add and Search Word - Data structure design

Posted on | Views:

Add and Search Word - Data structure design

Design a data structure that supports the following two operations. search(word) can search a literal word or a regular expression string containing only letters a-z or .. . means it can represent any one letter.
（设计一种数据结构支持正则查询）

1
2
void addWord(word)
bool search(word)

Example:



1. 回溯法

由于包含正则项的匹配，使用回溯法，回溯法一般通过 DFS 完成，具体实现过程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import collections

class Node:
    def __init__(self):
        self.children = collections.defaultdict(Node)
        self.is_word = False

class WordDictionary:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = Node()

    def addWord(self, word: str) -> None:
        """
        Adds a word into the data structure.
        """
        current = self.root
        for w in word:
            current = current.children[w]
        current.is_word = True
    
    def dfs(self, current, word, i):
        if i == len(word):
            return current.is_word
        w = word[i]
        if w == '.':
            for child in current.children:
                if current.children[child] and self.dfs(current.children[child], word, i+1):
                    return True 
            return False
        else:
            if not current.children.get(w):
                return False
            else:
                return self.dfs(current.children[w], word, i+1)  
            
    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.dfs(self.root, word, 0)
            
# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)

2. 字典

由于.能切只能匹配一个字符，因此字符串的长度是恒定的，因此可以根据字符串的长度来进行哈希，具体实现过程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import collections

class WordDictionary:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.word_dict = collections.defaultdict(list)

    def addWord(self, word: str) -> None:
        """
        Adds a word into the data structure.
        """
        if word:
            self.word_dict[len(word)].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.
        """
        if not word:
            return False
        if '.' not in word:
            if word in self.word_dict[len(word)]:
                return True
        for v in self.word_dict[len(word)]:
            match = True
            # match xx.xx.x with yyyyyyy
            for i, ch in enumerate(word):
                if ch != v[i] and ch != '.':
                    match = False
                    break
            if match:
                return True
        return False
        
# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)