LeetCode

LeetCode-Trie-search regular expression

问题描述：

设计一个数据结构，并且实现两个方法：

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

其中word中孩子包含26个字母，而需要查找的pattern是26个字母和’.’，’.’可以匹配任何一个字母，如下：

1
2
3
4
5
6
7
addWord("bad")
addWord("dad")

search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

实现：

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

class TrieNode{
public:
    bool is_word;
    TrieNode* next[26];
    TrieNode(bool b=false){
        is_word = b;
        memset(next, NULL, sizeof(next));
    }
};

class WordDictionary {
private:
    TrieNode* root;
/// 后续遍历，销毁Trie
    void clear(TrieNode* root){
        for (int i=0;i<26;i++){
            if (root->next[i] != nullptr)
                clear(root->next[i]);
        }
        delete root;
    }
/// 递归实现匹配
    bool search_(const char* word, TrieNode* root){
        // 遍历word中每一个字符
		for (int i=0; word[i]&&root; i++){
            // 如果当前字符　是26个字母，指针向下移动即可
			if (word[i] != '.'){
				root　=　root->next[word[i]-'a'];
			}
            // 如果当前字符是'.'，
            else{
				TrieNode* node = root;
                // 遍历这个结点next所有域，
				for (int j=0;j<26;j++){
					root = node->next[j];
					if (search_( word+i+1, root)){
						return true;
					}
				}
			}
		}
		return root && root->is_word;
	}
    
public:
    WordDictionary() {
        root = new TrieNode();
    }
    ~WordDictionary(){
        clear(root);
    }
    
    void addWord(string word) {
        TrieNode* tmp = root;
        for (int i=0;i<word.size();i++){
            if (tmp->next[word[i]-'a'] == nullptr)
                tmp->next[word[i]-'a'] = new TrieNode();
            tmp = tmp->next[word[i]-'a'];
        }
        tmp->is_word = true;
    }
    
/// 匹配入口
    bool search(string word){
		return search_(word.c_str() ,root);
	}
};

体会递归函数：search_()。