今天的題單：

• Implement Trie (Prefix Tree)

• Coin Change

208. Implement Trie (Prefix Tree)

實作 Trie (字典樹)。題目限制單字只會有小寫英文字母，所以我實作的時候每個 node 都直接開長度 26 的 vector 存 children，並且每個 node 存一個字母。

class Trie {
public:
    class Node {
    public:
        Node(char s): c(s), eof(false) {
            child.resize(26, nullptr);
        }
        
        char c;
        bool eof;
        vector<Node*> child;
    };

    Trie() {
        this->root = new Node('S');
    }
    
    void insert(string word) {
        Node* curr = this->root;
        for (auto& s : word) {
            if (curr->child[s-'a'] == nullptr) {
                // create new node
                curr->child[s-'a'] = new Node(s);
            }
            curr = curr->child[s-'a'];
        }
        curr->eof = true;
    }
    
    bool search(string word) {
        Node* curr = this->root;
        for (auto& s : word) {
            if (curr->child[s-'a'] == nullptr || curr->child[s-'a']->c != s) {
                return false;
            }
            curr = curr->child[s-'a'];
        }
        return curr->eof;
    }
    
    bool startsWith(string prefix) {
        Node* curr = this->root;
        for (auto& s : prefix) {
            if (curr->child[s-'a'] == nullptr || curr->child[s-'a']->c != s) {
                return false;
            }
            curr = curr->child[s-'a'];
        }
        return true;
    }
private:
    Node* root;
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

322. Coin Change

思路: 用 DP，依序計算 amount = k 時需要最少能用幾個硬幣組成。

Example:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

硬幣數量最小單位是 1，可以推出計算「amount = k 的解」需要先算所有「amount = k - 可用硬幣面額」的解，找出其中最小值後 + 1。

初始狀態:

• 設計一個 array: dp[i] <- amount = i 時需要最少能用幾個硬幣

• 對於 amount 最少需要的硬幣數量是「用所能整除的硬幣最大面額」的商。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1, INT_MAX-1);

        sort(coins.begin(), coins.end());

        // Init
        for (int i = 0; i <= amount; i++) {
            for (int j = 0; j < coins.size(); j++) {
                if (i >= coins[j] && i % coins[j] == 0) {
                    dp[i] = min(dp[i], i / coins[j]);
                }
            }
        }
        dp[0] = 0; // special case

        for (int i = 0; i <= amount; i++) {
            for (int j = 0; j < coins.size(); j++) {
                if (i >= coins[j]) {
                    dp[i] = min(dp[i-coins[j]] + 1, dp[i]);
                }
            }
        }

        return dp[amount] >= INT_MAX-1 ? -1 : dp[amount];

    }
};