2976. 轉換字符串的最小成本 I

思路

題目給了轉換單字的成本列表，可以利用這張表來找到從一個單字轉換到其他單字的最小成本。
因為要找到「所有點」到「所有點」的最短路徑，使用 Floyd 演算法去遍歷。

程式碼

Floyd

class Solution {
public:
    long long minimumCost(string source, string target, vector<char>& original, vector<char>& changed, vector<int>& cost)
    {
        const int n = 26;
        vector<vector<int>> graph(n, vector<int>(n, INT_MAX));
        for(int i = 0; i < n; ++i) {
            graph[i][i] = 0; // 轉換成自己的成本為 0 
        }
        for(int i = 0; i < original.size(); ++i) {
            int from = original[i] - 'a', to = changed[i] - 'a', weight = cost[i];
            graph[from][to] = min(graph[from][to], weight); // 紀錄存在路徑的最小權重
        }
        for(int k = 0; k < n; ++k) {
            for(int i = 0; i < n; ++i) {
                if(graph[i][k] == INT_MAX) { // 如果 graph[i][k] 沒路，第三層迴圈就沒必要開始
                   continue; 
                }
                for(int j = 0; j < n; ++j) {
                    if(i != j && graph[k][j] != INT_MAX) {
                        graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]); // 利用 k 當中轉的成本，跟現有路徑比較
                    }
                }
            }
        }
        long long res = 0;
        for(int i = 0; i < source.size(); ++i) { // 現在成本都已經是最小
            int from = source[i] - 'a', to = target[i] - 'a';
            if(graph[from][to] == INT_MAX) return -1; // 無法轉換
            res += graph[from][to]; 
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(V^3N)$
• 空間複雜度：$O(V^2)$，V=26