691. 貼紙拼詞

思路

給定幾張貼紙，上面寫了一些英文單字，再給定目標字串 $target$ ，問至少要幾張貼紙，才能將目標字串給組合出來。
貼紙有無限張，並且可以隨機裁切，比如 $abk$ 可以拿來拼 $bca$ 中的兩個字元。

因為貼紙可以隨意裁切，因此順序並不重要，只有每個字元的數量才重要。 假如現在目標字串是 $aaabbbcck$ ，兩張貼紙： $aabb,ccddk$

• $aabb$ ，它可以滿足四個字元。
• 接下來的問題，變成 $abcck$ 需要幾張貼紙滿足條件，假設答案是 $x_1$ 。
• $ccddk$ ，它可以滿足三個字元。
• 接下來的問題，變成 $aabb$ 需要幾張貼紙滿足條件，假設答案是 $x_2$ 。

對於 $abcck$ 與 $aabbk$ 這兩個子問題，我們能用完全相同的方式去解，
因此 queue 當中擺放的，是當前要處理的字串，一直到處理的字串是空，就代表到達目標狀況了 ，此時在第幾次展開，就代表使用了幾張貼紙。

優化方面，在上面的例子當中，第一步的展開，我們能查看目標字串的第一個字元，這時是 $a$ 。
既然不論如何都需要消掉這個 $a$ ，在這步當中，我們就只要把包含 $a$ 的字串 $aabb$ 拿去配對就好，而 $ccddk$ 就不用配，來減少每次分支的數量。

程式碼

記憶化搜索

class Solution {
private:
    static const int MX = 401;
    string q[MX];
    string f(string& cur, string& s) { // 把 s 貼紙用在 cur 上
        // 兩個字串都已經排序，可利用這個特性
        string res;
        int i = 0, j = 0;
        while(i < cur.length()) {
            if(j == s.length()) { // 無法消除
                res += cur[i++];
            }
            else {
                if(cur[i] == s[j]) {
                    i++;
                    j++;
                }
                else if(cur[i] > s[j]) { // 兩個不同，若 cur[i] 比較大, 移動 j
                    j++;
                }
                else { // cur[i] 比較小，沒希望了，不可能配對
                    res += cur[i++];
                }
            }
        }
        return res;
    }
public:
    int minStickers(vector<string>& stickers, string target) {
        int n = stickers.size();
        ranges::sort(target);
        vector<vector<string>> graph(26); // 紀錄能處理特定字元的單字
        unordered_map<string, bool> visited; // 紀錄那些狀態有被走訪過，先被走訪的，一定要比後面被走訪的答案來的好
        visited[target] = true;
        for(auto& s : stickers) {
            ranges::sort(s);
            for(int i = 0; i < s.length(); i++) {
                if(i == 0 || s[i - 1] != s[i]) { // 避免掉重複字元            
                    graph[s[i] - 'a'].push_back(s); // s 包含字元 c, 可以用來消除字元 c 
                }
            }
        }
        int step = 0;
        int l = 0, r = 0;
        q[r++] = target;
        while(l < r) {
            int size = r - l;
            while(size--) {
                string cur = q[l++];
                for(string& s : graph[cur[0] - 'a']) {
                    // 兩個字串都經過排序
                    string next = f(cur, s);
                    if(next == "") { // 到達目標狀態，返回步數
                        return step + 1;
                    }
                    if(!visited[next]) { // 沒來到過這個狀態，需要後續計算
                        visited[next] = true;
                        q[r++] = next;
                    }
                }
            }
            step++;
        }
        return -1;
    }
};

複雜度分析

• 時間複雜度：$O(2^m\times{n}\times{m})$
• 空間複雜度：$O(2^m\times{m})$