題目： LeetCode - 211. Add and Search Word - Data structure design

題目說明

設計一個資料結構，完成題目要求的兩個函式，void addWord(string word)、bool search(string word)。在 word 中， . 代表任意字符。

解題思路

使用字典樹來實現，關於字典樹的做法可參考本篇文章：LeeCode - 208 解題紀錄。

  • void addWord(string word)：
    和字典樹的做法一模一樣，不再贅述。

  • bool search(string word)：
    由於題目多了 . 的特殊情況，所以我們額外定義一個函式，bool exist(string& word, int pos, node* ptr) pos 代表目前要檢查的字元位置，當 word[pos] 不為 . 時，直接往下檢查即可。否則 ptr->child[] 全部都要往下檢查。

參考解法

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
69
70
71
72
73
74
75
// fast IO
static auto __ = []()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();

class node
{
public:
    node* child[26];
    bool isWord;
    
    node():isWord(false)
    {
        for(auto& p : child)
            p = nullptr;
    }
    
    ~node()
    {
        for(auto& p : child)
            delete p;
    }
};

class WordDictionary {
public:
    /** Initialize your data structure here. */
    WordDictionary() {
        root = new node();
    }
    
    ~WordDictionary() {
        delete root;
    }
    
    /** Adds a word into the data structure. */
    void addWord(string word) {
        auto ptr = root;
        for(auto c : word)
        {
            int index = c - 'a';
            if(!ptr->child[index])
                ptr->child[index] = new node();
            ptr = ptr->child[index];
        }
        ptr->isWord = true;
    }
    
    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    bool search(string word) {
        return exist(word, 0, root);
    }
    
    bool exist(string& word, int pos, node* ptr)
    {
        if(!ptr)
            return false;
        if(pos == word.size())
            return ptr->isWord;
        auto c = word[pos];
        if(c != '.')
            return exist(word, ++pos, ptr->child[c - 'a']);
        for(auto& child : ptr->child)
            if(exist(word, pos + 1, child))
                return true;
        return false;
    }

private:
    node* root;
};

2020-08-15 重寫

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
// fast IO
static auto __ = []()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();

class TrieNode
{
public:
    TrieNode* child[26];
    bool isWord;
    
    TrieNode() : isWord(false) { for(auto& p : child) p = nullptr; }
    
    ~TrieNode() { for(auto& p : child) delete p; }
};

class WordDictionary {
public:
    /** Initialize your data structure here. */
    WordDictionary() { root = new TrieNode(); }
    
    ~WordDictionary() { delete root; }
    
    /** Adds a word into the data structure. */
    void addWord(string word) {
        auto p = root;
        for(auto c : word)
        {
            if(!p->child[c - 'a']) p->child[c - 'a'] = new TrieNode();
            p = p->child[c - 'a'];
        }
        p->isWord = true;
    }
    
    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    bool search(string word) { return exist(word, 0, root); }
    
    bool exist(string& word, int pos, TrieNode* p)
    {
        if(!p) return false;
        if(pos == word.size()) return p->isWord;
        auto c = word[pos];
        if(c != '.') return exist(word, ++pos, p->child[c - 'a']);
        for(auto& child : p->child) if(exist(word, (++pos)--, child)) return true;
        return false;
    }

private:
    TrieNode* root;
};