2977. 轉換字符串的最小成本 II

前置題目：2976. 轉換字符串的最小成本 I

思路

在前置題目當中，只會有字元跟字元之間的交換，現在則是字串跟字串的交換。
之前的 a ~ z 可以用 0 ~ 25 表示，用-'a'操作就可以做到，但是字串不行，
因此這題需要先給所有出現的字串一個獨特的id。

知道了id之後，利用 Floyd 演算法找到字串到其他字串轉換的最小成本。

在知道最小成本之後，還要套用一系列交換，獲取最小成本

1. 字串要有獨特的id
2. 一系列的交換可以是任何長度，所以每向前增長現在看到的字元，就要看看能否交換，
   而判斷能否交換，首先得知道交換前後的字串存不存在。
   • 比如現在source = "abcd"，target = "efgh"
     • 一開始看第一個字元 a，e，假設不存在於original跟changed中。
     • 看兩個字元 ab，ef，假設存在，套用交換，成本 3，這時參考答案就會加入 3 + 「"cd"和"gh"去找最小成本」。

需要有id，又需要判斷存不存在，可以用哈希表，或是前綴樹，因為字元會往外擴，比如 $a\to{ab}\to\dots$ 用前綴樹會比較合適。

程式碼

前綴樹 + Floyd + 記憶化搜索

struct TrieNode {
    int id = -1;
    TrieNode* nexts[26]{}; // 一共有 26 條路可以走
};
class Trie {
public:
    int cnt;
    TrieNode* root;
    Trie() : root(new TrieNode()), cnt(0) {}
    int insert(string s) {
        TrieNode* cur = root;
        for(char ch : s) {
            int index = ch - 'a';
            if(cur->nexts[index] == nullptr) { // 不存在就開拓新的路
                cur->nexts[index] = new TrieNode();
            }
            cur = cur->nexts[index];
        }
        if(cur->id == -1) {// 第一次插入 
            cur->id = cnt++;
        }
        return cur->id;
    }
};
class Solution {
public:
    long long minimumCost(string source, string target, vector<string>& original, vector<string>& changed, vector<int>& cost) {
        int n = original.size();
        vector<vector<int>> dist(n * 2, vector<int>(n * 2, INT_MAX / 2)); // dist[字串1編號][字串2編號] = 最短路徑
        for(int i = 0; i < n * 2; i++) dist[i][i] = 0; // 自己走到自己的最小路徑 0
        
        // 為了讓字串編號，使用字典樹，也可以用哈希表
        Trie trie;
        for(int i = 0; i < n; ++i) {
            int x_id = trie.insert(original[i]);
            int y_id = trie.insert(changed[i]);
            dist[x_id][y_id] = min(dist[x_id][y_id], cost[i]);
        }

        // 計算最短路徑
        for(int k = 0; k < trie.cnt; ++k) {
            for(int i = 0; i < trie.cnt; i++) {
                if(dist[i][k] == INT_MAX / 2) { // i 無法走到 k, 就不需要進入第三層迴圈了
                    continue;
                }
                for(int j = 0; j < trie.cnt; j++) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }

        // 算出最終答案
        int m = source.size();
        vector<long long> memo(m, -1); // 字串對應的 id 
        auto dfs = [&](this auto&&dfs, int i) -> long long {
            if(i >= m) { // 越界   
                return 0;
            }
            long long& res = memo[i]; // 注意引用
            if(res != -1) return res; // 有算過
            res = LLONG_MAX / 2;
            if(source[i] == target[i]) {
                res = dfs(i + 1);
            }
            TrieNode* node1 = trie.root;
            TrieNode* node2 = trie.root;
            for(int j = i; j < m; j++) { // 後面可以結束的位置. 每次前進一步，字典樹檢查字串是否存在
                node1 = node1->nexts[source[j] - 'a'];
                node2 = node2->nexts[target[j] - 'a']; 
                if(!node1 || !node2) { // 走到結尾, 無法繼續了
                    break;
                }
                if(node1->id < 0 || node2->id < 0) { // 字串不存在，現在走到一半
                    continue;
                }
                if(dist[node1->id][node2->id] < INT_MAX / 2) {
                    res = min(res, dist[node1->id][node2->id] + dfs(j + 1)); // 在現在的位置套用交換, 遞迴加入後續解答 dfs(j + 1)
                }
            }
            return res;
        };

        long long res = dfs(0);
        return res < LLONG_MAX / 2 ? res : -1;
    }
};

複雜度分析

• 時間複雜度：$O(m^2+mn+n^3)$，m = source.length，n = cost.length，記憶化搜索 $O(m^2)$ ，前綴樹 $O(mn)$，Floyd $O(n^3)$。
• 空間複雜度：$O(m+mn+n^2)$ 前綴樹 $O(mn)$，Floyd $O(m^2)$