Trie (字典樹) - Design Add and Search Words Data Structure

發表於 分類於 閱讀次數： 文章字數： 785 所需閱讀時間 ≈ 3 分鐘

前言

寫完上一篇Implement Trie (字典樹)後，沒過兩天LeetCode每日一題又出現Trie的題目了(笑)，題目是211. Design Add and Search Words Data Structure，簡單來說就是字典樹加上一點正規表達(regular expression)的概念，舉例來說trie裡有bad，那搜尋b.d的話也要回傳true，詳細題目一樣自己到LeetCode去看囉。

解題思路

如果不考慮正規表達的話，那其實就是最基本的Trie，還不了解trie的話可以參考前一篇文章！但現在多了這個特殊條件後，我們就需要去考慮所有可能，方法是寫一個dfs(Depth First Search)的輔助函式，遇到.的話就將當前節點下的所有子節點再帶入dfs，看最後有沒有符合的單字，只要有其中一個子節點符合的話會提前回傳true，都沒有的話就回傳false。

我們以下面的圖片來說明步驟，假設我們今天搜尋b.t：

  1. 跟一般的trie一樣，我們會先確認root下有沒有b這個節點，有的話就走到這個節點上。
  2. 因為第二個字是.，表示ba跟bo都是我們可以走的路徑，因此我們兩條路都要去訪問，依字母順序我們先訪問ba。
  3. ba下面雖然有節點bat，但他不是單字的結尾，所以我們跳出這條路徑。
  4. 我們回到上一層，改走bo這條路徑。
  5. bot符合我們要找的答案，並且他也是單字的結尾，因此回傳true。

trie

方法一: Pointers (C++)

重點

  • dfs除了要傳入節點curr，也要記錄目前走到第單字中的第幾個位置start。
  • 遇到.的話就對所有可能路徑再做一次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
49
50
51
52
53
54
55
56
struct Node{
    Node* children[26];
    bool is_end = false;
};

class WordDictionary {
private:
    Node* root;
    int n;
    string word;

    bool dfs(Node* curr, int start){
        for (int i=start; i<n; i++){
            // 遇到 .
            if (word[i] == '.'){
                // 用迴圈造訪所有可能路徑
                for (Node* next: curr->children){
                    // 路徑不可為空 && 該路徑有符合答案者
                    if (next!=nullptr && dfs(next, i+1)){
                        // 提前回傳 true
                        return true;
                    }
                }
                // 全部路徑無答案，回傳 false
                return false;
            }else if (curr->children[word[i]-'a'] != nullptr){
                curr = curr->children[word[i]-'a'];
            }else{
                return false;
            }
        }
        return curr->is_end;
    }

public:
    WordDictionary() {
        root = new Node();
    }
    
    void addWord(string word) {
        Node* curr = root;
        for (char w: word){
            if (curr->children[w-'a'] == nullptr){
                curr->children[w-'a'] = new Node();
            }
            curr = curr->children[w-'a'];
        }
        curr->is_end = true;
    }
    
    bool search(string word) {
        this->n = word.size();
        this->word = word;
        return dfs(root, 0);
    }
};

方法二: Hash Table (Python)

重點

  • 注意要避開#因為他不是一個路徑，否則會報錯。
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
class WordDictionary:
    def __init__(self):
        self.root = {}

    def addWord(self, word: str) -> None:
        curr = self.root
        for w in word:
            if w not in curr:
                curr[w] = {}
            curr = curr[w]
        curr["#"] = True

    def search(self, word: str) -> bool:
        n = len(word)

        def dfs(curr, start):
            for i in range(start, n):
                w = word[i]
                # 遇到 .
                if w == ".":
                    # 用迴圈造訪所有可能路徑
                    for c in curr:
                        # 避開結尾標記 && 該路徑有符合答案者
                        if c!="#" and dfs(curr[c], i+1):
                            # 提前回傳 true
                            return True
                    # 全部路徑無答案，回傳 false
                    return False
                elif w in curr:
                    curr = curr[w]
                else:
                    return False
            return "#" in curr

        return dfs(self.root, 0)