題目： LeetCode - 1032. Stream of Characters

題目說明

完成一個 Class，裡面包含兩個函式。

  • StreamChecker(vector<string>& words)：給一個字串的陣列，表示字典。
  • bool query(char letter)：可以想像成呼叫一次就是使用者打了一個字，檢查使用者打的前幾個字中是否有包含於字典中的單詞。

解題思路

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

只要建一個顛倒的字典樹即可。例如 cd 就建成 dc。

  • StreamChecker(vector<string>& words)：普通字典樹的建造。
  • bool query(char letter)：呼叫時先將 letter 加入到字串中，接著從後面開始往前檢查。

參考解法

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
// 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() : isWord(false) { for(auto& ptr : child) ptr = nullptr; }
    
    ~TrieNode() { for(auto& ptr : child) delete ptr; }
    
    void build(string& str, int idx)
    {
        if(idx == -1) { isWord = true; return; }
        if(!child[str[idx] - 'a']) child[str[idx] - 'a'] = new TrieNode();
        child[str[idx] - 'a']->build(str, --idx);
    }
    
    bool search(string& str, int idx)
    {
        if(idx == -1 || isWord) return isWord;
        return child[str[idx] - 'a'] ? child[str[idx] - 'a']->search(str, --idx) : false;
    }
    
private:
    TrieNode* child[26];
    bool isWord;
};
    
class StreamChecker {
public:
    StreamChecker(vector<string>& words) {
        root = new TrieNode();
        for(auto& word : words) root->build(word, word.size() - 1);
    }
    
    ~StreamChecker() { delete root; }
    
    bool query(char letter) { return root->search(curstr += letter, curstr.size() - 1); }

private:
    TrieNode* root;
    string curstr;
};