# Leetcode刷題學習筆記 -- Trie
## Introduction
因為C++沒有內建trie的data struct，所以必須自己implement。

### 使用unordered_map來實作

class trie{
    struct node{
        unordered_map<char, node *> m;
        bool isWord;
        string word;
    };
    node *root;
    void addWord(string& s) {
        node *p = root;
        for(auto& c : s) {
            if(!p->m.count(c))
                p->m[c] = new node();
            p = p->m[c];
        }
        p->isWord = true;
        p->word = s;
    } 
public:
    trie() {
        root = new node();
    }
    trie(vector<string>& words) : trie() {
        for(auto& w : words)
            addWord(w);
    }
};

使用上面的程式碼，增加一個字串"OATH"，可以得到以下的結構。其中紀錄這個字串的屬性的isWord和word是在下一個node中。參考[Word Search II](https://hackmd.io/QDEA_oTZTwOqDc35dWwOHw?both#212-Word-Search-II)


### [421. Maximum XOR of Two Numbers in an Array(Medium)](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/)
給你一個vector<int> nums，求出任兩個數字最大的XOR值。
> 1. 建立trie來記錄數字間bit的差別。
> 2. 得到最大的XOR差就是把目前的num和trie中，如果有bit反向就取反向的bit，這樣就會得到最大的XOR。

class node{
    public:
    node *v0;
    node *v1;
};

class trie{
    node *root;
    public:
    trie() {
        root = new node();
    }
    void insert(int num) {
        node *p = root;
        for(int i = 31; i >= 0; --i) {
            int bit = (num >> i) & 1;
            if(bit) {
                if(!p->v1) p->v1 = new node();
                p = p->v1;
            } else {
                if(!p->v0) p->v0 = new node();
                p = p->v0;
            }
        }
    }
    int getMaxXor(int num) {
        node *p = root;
        int rtn{0};
        for(int i = 31; i >= 0; --i) {
            int bit = (num >> i) & 1;
            if(bit) { // search bit 0
                if(p->v0) {
                    rtn |= 1 << i;
                    p = p->v0;
                } else
                    p = p->v1;
            } else {    // search bit 1
                if(p->v1) {
                    rtn |= 1 << i;
                    p = p->v1;
                } else
                    p = p->v0;
            }
        }
        return rtn;        
    }
};

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        int rtn{0}, val;
        trie t;
        for(auto& n : nums) {
            t.insert(n);
            val = t.getMaxXor(n);
            rtn = max(rtn, val);
        }
        return rtn;
    }
};

### [211. Design Add and Search Words Data Structure(Medium)](https://leetcode.com/problems/design-add-and-search-words-data-structure/)
實現addWord和search的功能，其中serch的字串可以有'.'代表任何字元。
> 1. 一樣使用trie來實現。
> 2. 當加入的word比較短的時候，==必須使用isWord來表示這個字是否結束。==

class node{
    public:
    array<node *, 26> word;
    bool isWord{false};
};

class WordDictionary {
    node *root;
public:
    /** Initialize your data structure here. */
    WordDictionary() {
        root = new node();
    }
    
    void addWord(string word) {
        node *p = root;
        for(int i = 0; i < word.length(); ++i) {
            if(p->word[word[i] - 'a'] == nullptr)
                p->word[word[i] - 'a'] = new node();
            p = p->word[word[i] - 'a'];
        }
        p->isWord = true;
    }
    
    bool _search(node *p, string word, int idx) {
        if(p == nullptr) return false;
        if(idx == word.length())
            return p->isWord ? true : false;
        char c = word[idx];
        if(c != '.') {
            if(p->word[c - 'a'] == nullptr) return false;
            else return _search(p->word[c - 'a'], word, idx + 1);
        } else {
            for(int i = 0; i < 26; ++i) {
                if(p->word[i] != nullptr && _search(p->word[i], word, idx + 1))
                    return true;
            }
            return false;
        }
    }
    
    bool search(string word) {
        node *p = root;
        return _search(p, word, 0);
    }
};

### [745. Prefix and Suffix Search](https://leetcode.com/problems/prefix-and-suffix-search/)
初始化給你一組vector<string> words, 然後在給你prefix和suffix來查詢符合的string最大的index。
> 1. 使用兩個trie分別來記錄prefix和suffix。
> 2. 紀錄每個prefix和suffix會用到的idx。

struct node{
    bool isWord;
    set<int> idx;
    vector<node *> list;
    node(): list(26) {};
};
class WordFilter {
   node *prefix, *suffix;
   void createTrie(node *root, string& str, int idx) {
       node *p = root;
       for(auto& c : str) {
           if(p->list[c - 'a'] == nullptr)
               p->list[c - 'a'] = new node();
           p = p->list[c - 'a'];
           p->idx.insert(idx);
       }
       p->isWord = true;
    }
    void createPrefix(string& str, int idx) {
        createTrie(prefix, str, idx);
    } 
    void createSuffix(string& str, int idx) {
        createTrie(suffix, str, idx);
    }
    void printTrie(node *root) {
        node *p = root;
        for(int i = 0; i < p->list.size(); ++i) {
            if(p->list[i] != nullptr) {
                cout << (char)(i + 'a') << ",";
                for(auto& n : p->list[i]->idx) cout << n << ",";
                cout << endl;
                printTrie(p->list[i]);
            }
        }
    }
    void print() {        
        cout << "prefix : " << endl;
        printTrie(prefix);
        cout << "suffix : " << endl;
        printTrie(suffix);     
    }
    set<int>* findPrefix(string& str) {
        return findTrie(prefix, str);
    }
    set<int>* findSuffix(string& str) {
        reverse(str.begin(), str.end());
        return findTrie(suffix, str);
    }
    set<int>* findTrie(node *root, string& str) {
        node *p = root;
        for(auto& c : str) {
            if(p->list[c - 'a'] == nullptr) return nullptr;
            p = p->list[c - 'a'];
        }
        return &p->idx;
    }
public:
    WordFilter(vector<string>& words) {
        prefix = new node();
        suffix = new node();
        for(int i = 0; i < words.size(); ++i) {
            createPrefix(words[i], i);
            reverse(words[i].begin(), words[i].end());
            createSuffix(words[i], i);
        }
        // time complexity  : O(N) N 為words的全部char數目(worse case)
        // space complexity : O(N) 2N個node
    }
    
    int f(string pfx, string sfx) {
        set<int>* p = findPrefix(pfx);
        set<int>* s = findSuffix(sfx);
        if(p == nullptr || s == nullptr) return -1;
        for(auto it = p->rbegin(); it != p->rend(); ++it) {
            if(s->count(*it)) return *it;
        }
        return -1;
        // time complexity  : O(M) M 為pfx和sfx全部的char數目
        // space complexity : O(1) 只需要兩個pointer
    }
};

但是上面的做法需要尋找兩個Trie。其實可以把suffix + prefix成為新的string來尋找。這樣的話，在建立trie的時候，必須也把所有可能的suffix加進去變成新字串。

class TrieNode {
public:
    bool isWord;
    unordered_map<char, TrieNode *> m;
    vector<int> idx; //紀錄這個字串的index
};
class WordFilter {
    TrieNode *root;
    void genTrie(string& str, int idx) {
        TrieNode *p = root;
        for(auto& c : str) {
            if(!p->m.count(c))
                p->m[c] = new TrieNode();
            p->idx.push_back(idx);
            p = p->m[c];
        }
        // 最後也要儲存index，不然到底會找不到index
        p->idx.push_back(idx);
        p->isWord = true;
    }
public:
    WordFilter(vector<string>& words) {
        root = new TrieNode();
        for(int i = 0; i < words.size(); ++i) {
            int sz = words[i].size();
            // 建立所有可能的suffix組合
            for(int j = sz - 1; j >= 0; --j) {
                string newstr = words[i].substr(j) + '#' + words[i];
                genTrie(newstr, i);
            }
        }
    }
    
    int f(string prefix, string suffix) {
        string query = suffix + "#" + prefix;
        TrieNode *p = root;
        for(auto& c : query) {
            if(!p || !p->m.count(c)) return -1;
            p = p->m[c];
        }
        return p->idx.back();
    }
};

但是這個做法的效率比第一次的還差，應該是必須建立所有suffix的可能，還有多了很多string的操作。
### [820. Short Encoding of Words](https://leetcode.com/problems/short-encoding-of-words/)
Encode一個vector<string>其中suffix一樣可以由較長的string取代，每個string的結尾都要有個'#'，試問最小的encoding長度。
> 1. 因為考慮suffix的比較，所以==把每個string反過來建立trie。==
> 2. 如果不排序必須紀錄每個string結尾的TrieNode，來計算最後的長度。
> 3. 如果string由長到短排序，則不必紀錄結尾的TrieNod但是time complexity會多個$O(NlogN)$
> 4. 此題亦可使用unordered_set來解，因為erase對unoudered_set來說只是$O(1)$

class Solution {
    struct TrieNode {
        unordered_map<char, TrieNode *> m;
    };
    TrieNode *root;
public:
    int minimumLengthEncoding(vector<string>& words) {
        root = new TrieNode();
        // 儲存每個word的最後一個TrieNode和長度
        vector<pair<TrieNode *, int>> lists;
        // 使用unordered_set<string>來刪除duplicate string
        for(auto& word : unordered_set<string> (words.begin(), words.end())) {
            TrieNode *cur = root;
            for(int i = word.size() - 1; i >= 0; --i) {
                if(!cur->m.count(word[i]))
                    cur->m[word[i]] = new TrieNode();
                cur = cur->m[word[i]];
            }
            lists.push_back(make_pair(cur, word.size() + 1));
        }
        int rtn = 0;
        for(auto& [node, sz] : lists) {
            // 如果沒有下一個char即為不重複string
            if(node->m.size() == 0) rtn += sz;    
        }
        return rtn;
    }
};

### [212. Word Search II](https://leetcode.com/problems/word-search-ii/)
給你一個vector<vector<char>> board和vector<string> words，找出在board中有出現words的字串。其中一個字串只能使用一次board上的字元。

> 1. 使用trie建立words
> 2. 尋找每個board上的字元，在trie中是否有匹配的string。
> 3. ==因為判斷使否為一個字串在下一個node，必須先前進判斷==

class trie{
    struct node{
        unordered_map<char, node *> m;
        bool isWord;
        string word;
    };
    node *root;
    void _searchWord(vector<vector<char>>& board, int y, int x, unordered_set<string>& rtn, node *p) {
        if(!p) return;
        if(y < 0 || x < 0 || y == board.size() || x == board[0].size() || board[y][x] == 0) return;
        char c = board[y][x];
        if(!p->m.count(c)) return;
        board[y][x] = 0;
        { // 必須在這邊前進，因為判斷是否為word在下一個node
            p = p->m[c];
            if(p->isWord) rtn.insert(p->word);
        }
        _searchWord(board, y + 1, x, rtn, p);
        _searchWord(board, y, x + 1, rtn, p);
        _searchWord(board, y - 1, x, rtn, p);
        _searchWord(board, y, x - 1, rtn, p);
        board[y][x] = c;
    }
public:
    trie() {
        root = new node();
    }
    trie(vector<string>& words) : trie() {
        for(auto& w : words)
            addWord(w);
    }
    void addWord(string& s) {
        node *p = root;
        for(auto& c : s) {
            if(!p->m.count(c))
                p->m[c] = new node();
            p = p->m[c];
        }
        p->isWord = true;
        p->word = s;
    }
    void searchWord(vector<vector<char>>& board, int y, int x, unordered_set<string>& rtn) {
        _searchWord(board, y, x, rtn, root);
    } 
};

class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        int m = board.size();
        int n = board[0].size();
        trie tr(words);
        
        unordered_set<string> rtn;
        for(int y = 0; y < m; ++y) {
            for(int x = 0; x < n; ++x) {
                tr.searchWord(board, y, x, rtn);
            }
        }
        return vector<string>(rtn.begin(), rtn.end());
    }
};

### [2352. Equal Row and Column Pairs](https://leetcode.com/problems/equal-row-and-column-pairs/description/)
給你vector<vector<int>> grid的二維陣列，找出每個座標[y, x]其中row-x和column-y相同的數目。
> 1. 這題很直覺的使用unordered_map<stirng, int>來統計數目，缺點是建立string比較花時間。
> 2. 另外比較每個數值，其實就像是Trie比較每個node，所以可以改用Trie來實現。
> 3. 另外考量release node的問題，改用shared_ptr來實現原本的C pointer(struct node*)。

class Solution {
    struct node{
        unordered_map<int, shared_ptr<node>> m;
        int cnt;
    };
    shared_ptr<node> root;
public:
    int equalPairs(vector<vector<int>>& grid) {
        int n = grid.size();
        if(n == 1) return 1;
        root = make_shared<node>();
        for(auto& r : grid) {
            shared_ptr<node> p(root);
            for(auto& n : r) {
                if(!p->m.count(n)) p->m[n] = make_shared<node>();
                p = p->m[n];
            }
            p->cnt++;
        }
        int ans = 0;
        for(int i = 0; i < n; ++i) {
            shared_ptr<node> p(root);
            for(int y = 0; y < n; ++y) {
                int& n = grid[y][i];
                if(!p->m.count(n)) break;
                p = p->m[n];
            }
            ans += p->cnt;
        }
        return ans;
    }
};

### [3045. Count Prefix and Suffix Pairs II](https://leetcode.com/problems/count-prefix-and-suffix-pairs-ii/description/)
> 1. 參考[lee215答案](https://leetcode.com/problems/count-prefix-and-suffix-pairs-ii/solutions/4744547/java-c-python-trie/)
> 2. 這邊的重點是字串abc __同時為__某個string 的prefix和suffix


class Solution {
    struct node{
        unordered_map<int, node*> m;
        int count;
    };
public:
    long long countPrefixSuffixPairs(vector<string>& words) {
        node* root = new node();
        long long ans{};
        for(const auto& w : words) {
            node* p = root;
            for(int i = 0, n = w.size(); i < n; ++i) {
                int val = w[i] * 128 + w[n - 1 - i];
                p = p->m.insert({val, new node()}).first->second;
                // 上面這行等同下面的意思，因為insert會return pair<iterator, bool>
                //if(!p->m.count(val)) p->m[val] = new node();
                //p = p->m[val];
                ans += p->count;
            }
            p->count++;
        }
        return ans;
    }
};

###### tags: `leetcode` `刷題`