題目解析： 實作一個字典樹（Trie），必須包含插入完整字串、搜尋完整字串，以及搜尋是否有特定前綴字串的三種功能。
解題思路： 先建一個 Node 結構，裡面放大小為 26 的指標陣列代表子節點，和一個布林值記錄是否為單字結尾。實作時設指標 q 從 root 開始，把輸入字元拆開對應陣列索引往下走，沒有節點就動態新增，最後把結尾標記設為 true。搜尋時一樣照著字元往下走，遇到空節點就回傳 false，走到最後再檢查布林值。

class Trie {
private:
    struct Node {
        Node* next[26] = {};
        bool isEnd = false;
    };
    Node* root;
public:
    Trie() {
        root = new Node();
    }
    
    void insert(string word) {
        Node* q = root;
        for (char c : word) {
            if (!q->next[c - 'a']) q->next[c - 'a'] = new Node();
            q = q->next[c - 'a'];
        }
        q->isEnd = true;
    }
    
    bool search(string word) {
        Node* q = root;
        for (char c : word) {
            if (!q->next[c - 'a']) return false;
            q = q->next[c - 'a'];
        }
        return q->isEnd;
    }
    
    bool startsWith(string prefix) {
        Node* q = root;
        for (char c : prefix) {
            if (!q->next[c - 'a']) return false;
            q = q->next[c - 'a'];
        }
        return true;
    }
};

題目解析： 給定產品陣列和搜尋字串，模擬搜尋框的自動補齊。每次多打一個字元，就要回傳最多 3 個符合前綴且字典序最小的產品名稱。
解題思路： 先把產品陣列由小到大排序。利用雙指標 l 和 r 包夾出符合前綴的範圍。每次多打一個字元，如果 l 或 r 所在的產品長度不夠，或是該位子的字元對不上，就把指標往內縮淘汰掉。處理完後，從 l 開始最多抓 3 個產品塞進陣列 v 裡面，再把 v 塞進 ans，重複直到打完字串。

class Solution {
public:
    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
        sort(products.begin(), products.end());
        vector<vector<string>> ans;
        int l = 0, r = products.size() - 1;
        
        for (int i = 0; i < searchWord.size(); i++) {
            char c = searchWord[i];
            vector<string> v;
            
            while (l <= r && (products[l].size() <= i || products[l][i] != c)) l++;
            while (l <= r && (products[r].size() <= i || products[r][i] != c)) r--;
            
            for (int j = 0; j < 3 && l + j <= r; j++) {
                v.push_back(products[l + j]);
            }
            ans.push_back(v);
        }
        return ans;
    }
};

題目解析： 從兩個等長陣列中挑出 k 個索引，分數為 nums1 選出數字的總和，乘上 nums2 選出數字的最小值，求最大可能分數。
解題思路： 分數的瓶頸在於 nums2 的最小值，所以先把兩陣列綁在一起，依照 nums2 由大到小排序。設一個由小到大排的優先佇列 v 裝 nums1 的數字，變數 sum 記總和。丟進迴圈跑，每次把 nums1 數字塞進 v 跟 sum 裡，若數量超過 k 就把 v 裡面最小的拔掉。只要湊滿 k 個，就結算當前分數並更新最大值 ans。

class Solution {
public:
    long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<pair<int, int>> arr;
        for (int i = 0; i < nums1.size(); i++) {
            arr.push_back({nums2[i], nums1[i]});
        }
        sort(arr.rbegin(), arr.rend());
        
        priority_queue<int, vector<int>, greater<int>> v;
        long long sum = 0, ans = 0;
        
        for (auto& it : arr) {
            v.push(it.second);
            sum += it.second;
            if (v.size() > k) {
                sum -= v.top();
                v.pop();
            }
            if (v.size() == k) {
                ans = max(ans, sum * it.first);
            }
        }
        return ans;
    }
};