# Trie

###### tags: `LeetCode筆記`


## :memo: 一、Basic Operations

### Insertion in Trie

1. Initialize: cur = root
2. for each char c in target string S:
3.      if cur does not have a child c:
4.          cur.children[c] = new Trie node
5.      cur = cur.children[c]
6. cur is the node which represents the string S

Usually, you will need to build the trie by yourself.
Building a trie is actually to call the insertion function several times.
But remember to **initialize a root node** before you insert the strings.

### Search in Trie

1. Initialize: cur = root
2. for each char c in target string S:
3.     if cur does not have a child c:
4.         search fails
5.     cur = cur.children[c]
6. search successes

## :memo: Implement Trie C
### 資料結構

typedef struct {
    struct Trie* child[26];
    bool is_word;
} Trie;

### Initialize a root node

Trie* trieCreate() {
    Trie* prefixTrie = (Trie*) malloc(sizeof(Trie));
    prefixTrie->is_word = false;
    for (int i = 0; i < 26; i++)
    {
        // prefixTrie->child[i] = (Trie*) malloc(sizeof(Trie));不用分配記憶體
        prefixTrie->child[i] = NULL;
    }
    
    return prefixTrie;
}

### Insertion

void trieInsert(Trie* obj, char * word) {
    if (obj == NULL)
    {
        return 0;
    }
    
    Trie* cur = obj;
    for (int i = 0; i < strlen(word); i++)
    {
        if (cur->child[word[i] - 'a'] == NULL)
        {
            cur->child[word[i] - 'a'] = trieCreate();
        }
        cur = cur->child[word[i] - 'a'];
    }
    cur->is_word = true;
}

### Search word

bool trieSearch(Trie* obj, char * word) {
    Trie* cur = obj;
    
    for (int i = 0; i < strlen(word); i++)
    {
        if (cur->child[word[i] - 'a'] == NULL)
        {
            return false;
        }
        cur = cur->child[word[i] - 'a'];
    }
    
    if (cur->is_word)
    {
        return true;
    }
    else
    {
        return false;
    }
    
    return true;
}

### Search prefix

bool trieStartsWith(Trie* obj, char * prefix) {
    Trie* cur = obj;
    
    for (int i = 0; i < strlen(prefix); i++)
    {
        if (cur->child[prefix[i] - 'a'] == NULL)
        {
            return false;
        }
        cur = cur->child[prefix[i] - 'a'];
    }
    
    return true;
}

### Free trie

void trieFree(Trie* obj) {
    if (!(obj))
    {
        free(obj);
        return;
    }
    for (int i = 0; i < 26; i++)
    {
        if (obj->child[i])
        {
            trieFree(obj->child[i]);
        }
    }
}

## :memo: Implement Trie C++ 第一種: Array (fast, watse space)

### 資料結構

#define N 26

A.
struct TrieNode {
    bool isWord;
    TrieNode* children[N];
};

B.
class TrieNode {
public:
    bool isWord;
    TrieNode* children[N];
    
    TrieNode() {
        isWord = false;
        memset(children, 0, sizeof(children));  // Initiallize all children to null
    }
};

### Initialize a root node

class Trie {
private:
    TrieNode* root;
    
public:
    Trie() {
        root = new TrieNode();
    }
}

### Insertion

class Trie {
public:
    void insert(string word) {
        TrieNode* curr = root;
        for (char c : word) {
            int index = c - 'a';
            if (!curr->children[index]) {
                curr->children[index] = new TrieNode();
            }
            curr = curr->children[index];
        }
        curr->isWord = true;
    }
}

### Search word

class Trie {
public:
    bool search(string word) {
        TrieNode* curr = root;
        for (char c : word) {
            int index = c - 'a';
            if (!curr->children[index]) {
                return false;
            }
            curr = curr->children[index];
        }
        return curr->isWord;
    }
}

### Search prefix

class Trie {
public:
    bool startsWith(string prefix) {
        TrieNode* curr = root;
        for (char c : prefix) {
            int index = c - 'a';
            if (!curr->children[index]) {
                return false;
            }
            curr = curr->children[index];
        }
        return true;
    }
}

## :memo: Implement Trie C++ 第二種: Map (slow, save space)

### 資料結構

struct TrieNode {
    bool flag;
    map<char, TrieNode*> next; 
};

### Initialize a root node

class Trie {
private:
    TrieNode* root;
public:
    /** Initialize your data structure here. */
    Trie() {
        root = new TrieNode();
    }
}

### Insertion

class Trie {
public:
    /** Inserts a word into the trie. */
    void insert(string word) {
        TrieNode* p = root;
        for (int i = 0; i < word.length(); ++i) {
            if ((p->next).count(word[i]) <= 0) {
                // insert a new node if the path does not exist
                (p->next).insert(make_pair(word[i], new TrieNode()));
            }
            p = (p->next)[word[i]];
        }
        p->flag = true;
    }
}

### Search word

class Trie {
public:
    /** Returns if the word is in the trie. */
    bool search(string word) {
        TrieNode* p = root;
        for (int i = 0; i < word.length(); ++i) {
            if ((p->next).count(word[i]) <= 0) {
                return false;
            }
            p = (p->next)[word[i]];
        }
        return p->flag;
    }
}

### Search prefix

class Trie {
public:
     /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        TrieNode* p = root;
        for (int i = 0; i < prefix.length(); ++i) {
            if ((p->next).count(prefix[i]) <= 0) {
                return false;
            }
            p = (p->next)[prefix[i]];
        }
        return true;
    }
}

## :memo: 二、Comparison with Hash Table

You might wonder why not use a hash table to store strings. Let's do a brief comparison between these two data structures. We assume there are N keys and the maximum length of a key is M.

1. Time Complexity
The time complexity to search in hash table is typically **O(1)**, but will be **O(logN)** in the worst time if there are too many collisions and we solve collisions using height-balanced BST.
The time complexity to search in Trie is **O(M)**.
**The hash table wins in most cases.**

2. Space Complexity
The space complexity of hash table is **O(M * N)**. If you want hash table to have the same function with Trie, you might need to store several copies of the key. For instance, you might want to store "a", "ap", "app", "appl" and also "apple" for a keyword "apple" in order to search by prefix. The space complexity can be **even much larger** in that case.
The space complexity of Trie is **O(M * N)** as we estimated above. But **actually far smaller** than the estimation since there will be a lot of words have the similar prefix in real cases.
**Trie wins in most cases.**

## :memo: Map Sum Pairs (Medium)

### 作法
用hashmap存已經有的key的val，diff = val - map[key]，資料結構有一個sum去記錄如過只到那裡的總和

struct TrieNode {
    TrieNode* child[26];
    int sum;
    
    TrieNode() {
        sum = 0;
        for (int i = 0; i < 26; i++) {
            child[i] = nullptr;
        }
    }
};

class MapSum {   
public:
    unordered_map<string, int> map;
    TrieNode* root;
    
    MapSum() {
        root = new TrieNode();
    }
    
    void insert(string key, int val) {
        int diff = val - map[key];
        TrieNode* curr = root;
        for (char c : key) {
            c -= 'a';
            if (curr->child[c] == nullptr) {
                curr->child[c] = new TrieNode();
            }
            curr = curr->child[c];
            curr->sum += diff;
        }
        map[key] = val;
    }
    
    int sum(string prefix) {
        TrieNode* curr = root;
        for (char c : prefix) {
            c -= 'a';
            if (curr->child[c] == nullptr) {
                return 0;
            }
            curr = curr->child[c];
        }
        return curr->sum;
    }
};

## :memo: Replace Words (Medium)

### 作法 C
這題要用到strtok()字串分割，首先複製sentence到一個新字串，接著進入字串分割的while迴圈，一開始判斷新字串是否是空格，並補上空格，接著進入TrieSearch(字串)回傳字數，然後重新分配res的記憶體空間，將找到的字串strncpy到res上，接著記錄res的index加上回傳字數，新字串的index加上搜尋字串的字數，繼續下一個分割字串的搜尋，結束後加上'\0'

struct Trie {
    struct Trie* next[26];
    bool isLeaf;
};

struct Trie* trieCreate() {
    struct Trie* n = (struct Trie*) malloc(sizeof(struct Trie));
    for (int i = 0; i < 26; i++)
    {
        n->next[i] = NULL;
    }
    n->isLeaf = false;
    
    return n;
}

void trieInsert(struct Trie* root, char* word) {
    if (root == NULL)
    {
        return 0;
    }
    
    struct Trie* p = root;
    for (int i = 0; i < strlen(word); i++)
    {
        if (p->next[word[i] - 'a'] == NULL)
        {
            p->next[word[i] - 'a'] = trieCreate();
        }
        p = p->next[word[i] - 'a'];
    }
    p->isLeaf = true;
}

int trieSearch(struct Trie* root, char* word) {
    if (root == NULL)
    {
        return 0;
    }
    struct Trie* p = root;
    
    int j = 0;
    int len = strlen(word);
    for (j = 0; j < len; j++)
    {
        if (p->next[word[j] - 'a'] == NULL)
        {
            return 0;
        }
        p = p->next[word[j] - 'a'];
        if (p->isLeaf == true)
        {
            break;
        }
    }
    if (p->isLeaf == false)
    {
        return 0;
    }
    
    return j + 1;
}

void trieDelete(struct Trie* root) {
    for (int i = 0; i < 26; i++)
    {
        if (root->next[i])
        {
            trieDelete(root->next[i]);
        }
    }
}

char * replaceWords(char ** dictionary, int dictionarySize, char * sentence) {
    struct Trie* t = trieCreate();
    char* res = (char*) malloc(sizeof(char));
    int resIdx = 0;
    int i = 0;
    
    for (i = 0; i < dictionarySize; i++)
    {
        trieInsert(t, dictionary[i]);
    }
    
    i = 0;
    int sntLen = strlen(sentence);
    char* csnt = (char*) malloc(sizeof(char) * (sntLen + 1));
    strcpy(csnt, sentence);
    csnt[sntLen] = '\0';
    char* pch = strtok(sentence, " ");
    int len = strlen(pch);
    
    while (pch)
    {
        if (csnt[i] == ' ')
        {
            res = realloc(res, sizeof(char) * (resIdx + 1));
            res[resIdx++] = csnt[i++];
        }
        int chars = trieSearch(t, pch);
        if (chars == 0)
        {
            chars = strlen(pch);
        }
        res = realloc(res, sizeof(char) * (resIdx + chars));
        strncpy(res + resIdx, pch, chars);
        resIdx += chars;
        i += strlen(pch);
        pch = strtok(NULL, " ");
    }
    res = realloc(res, sizeof(char) * (resIdx + 1));
    res[resIdx] = '\0';
    
    trieDelete(t);
    
    return res;   
}

### 作法 C++

class TrieNode {
public:
    TrieNode* child[26];
    bool isEnd;
    
    TrieNode() {
        this->isEnd = false;
        for (int i = 0; i < 26; i++) {
            this->child[i] = nullptr;
        }
    }    
};

class Solution {
    TrieNode* newNode;
public:
    string check(string word) {
        TrieNode* t = newNode;
        string s = "";
        
        for (auto i : word) {
            if (!t->child[i - 'a']) {
                break;
            }
            s += i;
            t= t->child[i - 'a'];
            if (t->isEnd) {
                return s;
            }
        }
        
        return word;
    }
    
    void insert(string word) {
        TrieNode* temp = newNode;
        
        for (auto l : word) {
            if (!temp->child[l - 'a']) {
                temp->child[l - 'a'] = new TrieNode();                
            }   
            temp = temp->child[l - 'a'];
        }
        
        temp->isEnd = true;
    }
    
    string replaceWords(vector<string>& dictionary, string sentence) {
        newNode = new TrieNode();
        for (auto s : dictionary) {
            insert(s);
        }
        istringstream ss(sentence);
        string word = "";
        string ans = "";
        
        for (; ss >> word; ) {
            ans += check(word);
            ans += ' ';
        }
        ans.pop_back();
        
        return ans;
    }
};

## :memo: Design Search Autocomplete System (Hard)

### 參考網站
https://hackmd.io/@kenjin/HymDpd-Nr

### 作法 C++

class AutocompleteSystem {
private:
    struct TrieNode {
        char c;
        bool isWord;
        unordered_map<char, TrieNode*> children;
        unordered_map<string, int> count;
        TrieNode(char c) : c(c), isWord(false) {}
    };
    
    void clear(TrieNode* root) {
        for (auto& child : root->children) {
            if (child.second != nullptr) clear(child.second);
        }
        
        delete root;
    }
    
    TrieNode* root;
    string prefix;
    
    void insert(string word, int count) {
        TrieNode* curr = root;
        for (char c : word) {
            if (curr->children[c] == nullptr) curr->children[c] = new TrieNode(c);
            curr = curr->children[c];
            curr->count[word] += count;
        }
        
        curr->isWord = true;
    }
    
    struct Compare {
        bool operator() (const pair<string, int>& lhs, const pair<string, int>& rhs) const {
            return lhs.second < rhs.second || (lhs.second == rhs.second && lhs.first > rhs.first);
        }
    }; 
    
public:    
    AutocompleteSystem(vector<string>& sentences, vector<int>& times) {
        root = new TrieNode(' ');
        prefix = "";
        
        for (int i = 0; i < sentences.size(); i++) insert(sentences[i], times[i]);
    }
    ~AutocompleteSystem() { clear(root); }
    vector<string> input(char c) {
        if (c == '#') {
            insert(prefix, 1);
            prefix = "";
            return {};
        }
        
        prefix += c;
        TrieNode* curr = root;
        for (char cc : prefix) {
            if (curr->children[cc] == nullptr) return {};
            curr = curr->children[cc];
        }
        
        priority_queue<pair<string, int>, vector<pair<string, int>>, Compare> q;
        for (auto& it : curr->count) q.push(it);
        
        vector<string> rs;
        
        int k = 3;
        while (!q.empty() && k-- > 0) {
            rs.push_back(q.top().first);
            q.pop();
        }
        
        return rs;
    }
};

## :memo: Add and Search Word - Data structure design (Medium)
Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

* WordDictionary() Initializes the object.
* void addWord(word) Adds word to the data structure, it can be matched later.
* bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.


### 作法 C++
這題要先判斷'.'的處理，'.'的處理就是檢查每一個字母是否有child，這裡要用遞回去做，如果不是'.'就是一般的搜尋，到底一樣判斷是否為word

class TrieNode {
public:
    TrieNode* children[26];
    bool isWord;
    
    TrieNode() {
        this->isWord = false;
        for (int i = 0; i < 26; i++) {
            this->children[i] = nullptr;
        }
    }
};

class WordDictionary {   
public:
    TrieNode* root;
    
    WordDictionary() {
        root = new TrieNode();
    }
    
    void addWord(string word) {
        TrieNode* curr = root;
        for (char c : word) {
            int index = c - 'a';
            if (!curr->children[index]) {
                curr->children[index] = new TrieNode();
            }
            curr = curr->children[index];
        }
        curr->isWord = true;
    }
    
    bool search_Dot(string word, TrieNode* obj) {
        TrieNode* curr = obj;
        int pos = 0;
        for (char c : word) {
            if (c == '.') {
                for (int i = 0; i < 26; i++) {
                    if (curr->children[i] != nullptr) {
                        string s = word.substr(pos + 1, word.length() - pos - 1);
                        if (search_Dot(s, curr->children[i])) {
                            return true;
                        }                        
                    }
                }
                return false;
            }
            else {
                int index = c - 'a';
                if (!curr->children[index]) {
                    return false;
                }
                curr = curr->children[index];
                pos++;
            }
        }
        if (curr->isWord == true) {
            return true;
        }
        else { 
            return false;
        }     
    }
    
    bool search(string word) {
        return search_Dot(word, root);
    }
};

## :memo: Practical Application II


## :memo: Maximum XOR of Two Numbers in an Array (Medium)


### 作法 C

struct TrieNode {
    struct TrieNode* children[2];
};

struct TrieNode* createNode() {
    struct TrieNode* node = (struct TrieNode *) malloc(sizeof(struct TrieNode));
    node->children[0] = NULL;
    node->children[1] = NULL;
    return node;
}

void insert(struct TrieNode* root, int val) {
    int i, bit;
    struct TrieNode* node = root;
    for (i = 31; i >= 0; i--)
    {
        bit = (val >> i) & 1;
        if (node->children[bit] == NULL)
        {
            node->children[bit] = createNode();
        }
        node = node->children[bit];
    }
}

int findMax(struct TrieNode* root, int val) {
    int i, bit, sum = 0;
    struct TrieNode* node = root;
    for (i = 31; i >= 0; i--)
    {
        bit = (val >> i) & 1;
        // 有相反就選相反，沒有就選一樣
        if (node->children[bit ^ 1] != NULL)
        {
            sum += (1 << i);
            node = node->children[bit ^ 1];
        }
        else
        {
            node = node->children[bit];
        }
    }
    return sum;
}

int freeNode(struct TrieNode* root) {
    if (root == NULL)
    {
        return;
    }
    freeNode(root->children[0]);
    freeNode(root->children[1]);
    free(root);
}

int findMaximumXOR(int* nums, int numsSize) {
    struct TrieNode *root = createNode();
    int i, max = 0, temp;
    for (i = 0; i < numsSize; i++)
    {
        insert(root, nums[i]);
    }
    
    for (i = 0; i < numsSize; i++)
    {
        temp = findMax(root, nums[i]);
        max = max > temp ? max : temp;
    }
    freeNode(root);
    return max;
}

### 作法 C++

class TrieNode {
public:
    TrieNode* child[2];
    
    TrieNode() {
        this->child[0] = nullptr;
        this->child[1] = nullptr;
    }
};

class Solution {
    TrieNode* root;
    
    void insert(int x) {
        TrieNode* t = root;
        bitset<32> bs(x);
        
        for (int j = 31; j >= 0; j--) {
            if (!t->child[bs[j]]) {
                t->child[bs[j]] = new TrieNode();
            }
            t = t->child[bs[j]];
        }
    }
    
public:
    int maxXOR(int n) {
        TrieNode* t = root;
        bitset<32> bs(n);
        int ans = 0;
        
        for (int j = 31; j >= 0; j--) {
            if (t->child[!bs[j]]) {     //Since 1^0 = 1 & 1^1 = 0, 0^0 = 0
                ans += (1 << j);
                t = t->child[!bs[j]];
            }
            else {
                t = t->child[bs[j]];
            }
        }
        
        return ans;
    }
    int findMaximumXOR(vector<int>& nums) {
        root = new TrieNode();
        
        for (auto& n : nums) {
            insert(n);
        }
        
        int ans = 0;
        for (auto n : nums) {
            ans = max(ans, maxXOR(n)); //updates the ans as we traverse the array & compute max XORs at each element.
        }
        
        return ans;
    }
};

### 作法 最快code C++

class Solution {
public:
    // Find the maximum XOR out of the numbers in sets [l1, r1) and [l2, r2).
    // These groups are assumed to be non-empty.
    int findMaximumXOR(std::vector<int> &nums, int l1, int r1, int l2, int r2, unsigned bit) {

    // Sanity assertion. Shouldn't have non-empty sets.
        if (l1 == r1 || l2 == r2) {
            throw logic_error{"shouldn't happen"};
        }

        // Split sets on zeros and ones.
        int s1{l1}, s2{l2}, res{};
        while (s1 < r1 && !(nums[s1] & bit)) {
            ++s1;
        }
        while (s2 < r2 && !(nums[s2] & bit)) {
            ++s2;
        }

        bit >>= 1;

        // One of the sets has one element. Try XORing between this element
        // and each element of the second set.
        if (l1 == r1 - 1) {
            while (l2 < r2) {
                res = std::max(res, nums[l1] ^ nums[l2++]);
            }
            return res;
        } else if (l2 == r2 - 1) {
            while (l1 < r1) {
                res = std::max(res, nums[l2] ^ nums[l1++]);
            }
            return res;
        }

        // Try to cross over if possible.
        auto diag1{l1 != s1 && s2 != r2}, diag2{l2 != s2 && s1 != r1};
        if (diag1) {
            res = findMaximumXOR(nums, l1, s1, s2, r2, bit);
        }
        if (diag2) {
            res = std::max(res, findMaximumXOR(nums, l2, s2, s1, r1, bit));
        }

        // Otherwise, the bits are all the same between the two groups.
        return res ? res : findMaximumXOR(nums, l1, r1, l2, r2, bit);
    }

    // This overload is to help find the first divergence point between
    // two numbers, so that we have two non-empty groups for the above
    // overload. This can be absorbed into the above overload, but it makes
    // the logic a little messier.
    int findMaximumXOR(std::vector<int> &nums, int l, int r, unsigned bit) {
        // 0 or 1 elements means the XOR is automatically 0.
        if (l >= r - 1) {
            return 0;
        }

        while ((nums[l] & bit) == (nums[r - 1] & bit)) {
            bit >>= 1;
        }

        // Split it into two groups.
        int s{l};
        while (s < r && !(nums[s] & bit)) {
            ++s;
        }

        // Return the result given the overload.
        return findMaximumXOR(nums, l, s, s, r, bit >> 1);
    }

    int findMaximumXOR(std::vector<int> &nums) {
        // Sort and deduplicate.
        std::sort(nums.begin(), nums.end());
        int j{};
        for (int i{}; i < nums.size(); ++i) {
            if (!i || nums[i] != nums[i - 1]) {
                nums[j++] = nums[i];
            }
        }

        return findMaximumXOR(nums, 0, j, 1u << 31);
    }
};

## :memo: Word Search II (Hard)

**Input:** board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
**Output:** ["eat","oath"]

### 參考網站
https://hackmd.io/@kenjin/0212_word-search-ii

### 作法 DFS + Trie C++

class TrieNode {
public:
    TrieNode* child[26];
    bool isWord;
    string word;
    
    TrieNode() {
        this->isWord = false;
        for (int i = 0; i < 26; i++) {
            this->child[i] = nullptr;
        }
    }
};

class Solution {
public:
    TrieNode* root;
    
    void insert(string word) {
        TrieNode* curr = root;    
        for (char c : word) {
            int index = c -'a';
            if (!curr->child[index]) {
                curr->child[index] = new TrieNode();
            }
            curr = curr->child[index];
        }
        curr->isWord = true;
        curr->word = word;
    }
    
    bool search(string word) {
        TrieNode* curr = root;    
        for (char c : word) {
            int index = c -'a';
            if (!curr->child[index]) {
                return false;
            }
            curr = curr->child[index];
        }
        if (curr->isWord == true) {
            return true;    
        }
        
        return false;
    }
    
    void dfs(vector<vector<char>>& board, int i, int j, TrieNode* t, set<string>& res, vector<vector<bool>>& visited) {
        if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size()) {
            return;            
        }
        
        char x = board[i][j] - 'a';
        t = t->child[x];
        if (visited[i][j] || !t) {
            return;
        }
        
        if (t->isWord) {
            res.insert(t->word);
        }
        
        visited[i][j] = true;        
        dfs(board, i + 1, j, t, res, visited);
        dfs(board, i - 1, j, t, res, visited);
        dfs(board, i, j + 1, t, res, visited);
        dfs(board, i, j - 1, t, res, visited);        
        visited[i][j] = false;
    }
        
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        set<string> res;
        root = new TrieNode();  // 不能再宣告TrieNode*(x)
        
        for (string s : words) {
            insert(s);
        }
             
        vector<vector<bool>> visited(board.size(),vector<bool>(board[0].size(),false));

        for(int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                dfs(board, i, j, root, res, visited);
            }
        }
        
        vector<string> ans(res.begin(), res.end());
        
        return ans;
    }
};

### 作法 最快code

class Solution {
public:
    int m, n;
    bool dfs(int ind, int i, int j, vector<vector < char>> &board, string &search) {
        if (ind == search.size()) {
            return true;
        }

        if (i >= 0 and i < m and j >= 0 and j < n) {
            if (board[i][j] != search[ind]) {
                return false;
            }
                
            char originalchar = board[i][j];
            board[i][j] = '$';

            bool ans = dfs(ind + 1, i + 1, j, board, search) ||
                dfs(ind + 1, i - 1, j, board, search) ||
                dfs(ind + 1, i, j + 1, board, search) ||
                dfs(ind + 1, i, j - 1, board, search);

            board[i][j] = originalchar;

            return ans;
        }
        return false;
    }

    vector<string> findWords(vector<vector < char>> &board, vector< string > &words)
    {
        m = board.size();
        n = board[0].size();

        vector<string> ans;
        vector<vector<pair<int, int>>> vp(27);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                vp[board[i][j] - 'a'].push_back({ i, j });
            }                
        } 

        int starta = 0;
        int enda = 0;

        for (auto ele: words) {
            if (ele[0] == 'a') {
                starta++;
            }                
            if (ele[ele.size() - 1] == 'a') {
                enda++;
            }                
        }

        bool reversehaikya = false;
        if (starta > enda) {
            reversehaikya = true;
            for (int i = 0; i < words.size(); i++) {
                reverse(words[i].begin(), words[i].end());
            }                
        }

        for (auto search: words) {
            bool flag = false;

            for (auto ele: vp[search[0] - 'a']) {
                flag = dfs(0, ele.first, ele.second, board, search);

                if (flag) {
                    if (reversehaikya) {
                        reverse(search.begin(), search.end());
                    }                      

                    ans.push_back(search);
                    break;
                }
            }
        }
        return ans;
    }
};

## :memo: Word Squares (Hard)

### 作法:

### 作法 C++

// Explanation
// wall      Try words      wall                     wall                      wall
// a...   => starting  =>   area      Try words      area                      area
// l...      with "a"       le..   => starting  =>   lead      Try words       lead
// l...                     la..      with "le"      lad.   => starting   =>   lady
//                                                             with "lad"

class Solution {
public:
    vector<vector<string>> wordSquares(vector<string>& words) {
        n = words[0].size();
        square.resize(n);
        for (string word : words)
            for (int i=0; i<n; i++)
                fulls[word.substr(0, i)].push_back(word);
        build(0);
        return squares;
    
    }
    int n;
    unordered_map<string, vector<string>> fulls;
    vector<string> square;
    vector<vector<string>> squares;
    void build(int i) {
        if (i == n) {
            squares.push_back(square);
            return;
        }
        string prefix;
        for (int k=0; k<i; k++)
            prefix += square[k][i];
        for (string word : fulls[prefix]) {
            square[i] = word;
            build(i + 1);
        }
    }
};

## :memo: Palindrome Pairs (Hard)

### 作法
https://leetcode.com/problems/palindrome-pairs/solution/

### 作法 C++

// 6mo - 15

class Solution {
public:
    // n - # of words
    // k - avg len of words
    // O(nkk), beats O(nnk)
    //
    // group words by length, and sorted groups by length
    // then check every word against word groups shorter
    // for words same len, only add once, because the other counter part will add too
    //
    // same complexity using trie, prefix tree

    // s[l, r] inclusive
    inline bool isPalindrome(const string &s, int l, int r) {
        while(l < r && s[l] == s[r]) {
            l++;
            r--;
        }
        return l >= r;
    }
    
    vector<vector<int>> palindromePairs(vector<string>& words) {
        // groups of words sorted by size
        map<int, unordered_map<string, int>> mm;
        for(int i=0; i<words.size(); i++) {   // O(n*log(k))
            mm[words[i].size()][string(words[i].rbegin(), words[i].rend())] = i;
        }
        
        vector<vector<int>> res;
        for(int i=0; i < words.size(); i++) { // O(n*k*k)
            auto w = words[i];
            
            for(auto & kv : mm) {
                auto & k = kv.first;
                auto & m = kv.second;
                if (k > w.size()) break;
                
                // same len word, add only once, for other word will add again as well
                if (k == w.size()) {
                    if (m.count(w) && m[w] != i) {
                        res.push_back({i, m[w]});
                    }
                    break;
                }
                
                // check back
                if (isPalindrome(w, k, w.size() - 1)) {
                    auto tgt = w.substr(0, k);
                    if (m.count(tgt)) {
                        res.push_back({i, m[tgt]});
                    }
                }

                // check front
                if (isPalindrome(w, 0, w.size() - k - 1)) {
                    auto tgt = w.substr(w.size() - k);
                    if (m.count(tgt)) {
                        res.push_back({m[tgt], i});
                    }
                }
            }
        }

        return res;
    }
};

// tests
// - same len words forming palindromes
// - ['abc', 'cba']
// - diff len words forming palindromes
// - 

## :memo: 刷題檢討
Trie先搞定基本的insert和search就好，基本上全都Hard題目，用C寫還會超時，C++才行Accepted，應用II的題目完全想不到跟Trie有啥關係，基本上是背誦解法了