🔗 🟡 2976. Minimum Cost to Convert String I 1882

tags: `Weekly Contest 377` `陣列(Array)` `圖(Graph)` `字串(String)` `最短路徑(Shortest Path)` `Floyd-Warshall`

題意

給定兩個長度為 $n$ ，全由小寫英文字母組成的字串 $\text{source}$ 和 $\text{target}$ ，以及兩個下標為 $0$ 開始的字元陣列 $\text{original}$ 和 $\text{changed}$ ，以及一個整數陣列 $\text{cost}$ ，其中 $\text{cost}[i]$ 代表將字元 $\text{original}[i]$ 更改為字元 $\text{changed}[i]$ 的花費。

對字串 $\text{source}$ 做一系列操作，每次操作可以選擇字串中的一個字元，並將其更改為另一個字元，並且花費為 $\text{cost}[i]$ 。操作結束後，若 $\text{source}$ 與 $\text{target}$ 相同，則返回操作的總花費，否則返回 $-1$ 。

返回將字串 $\text{source}$ 轉換為字串 $\text{target}$ 所需的最小成本。如果不可能完成轉換，則傳回 $-1$ 。

注意，可能存在下標 $i$ 、 $j$ 使得 $\text{original}[j] == \text{original}[i]$ 且 $\text{changed}[j] == \text{changed}[i]$ 。

思路：Floyd-Warshall 最短路徑

由範例中可以得出，對於將字元 $a$ 轉換為 $c$ ，可以由中間的字元 $b$ 來轉換，即 $a \rightarrow b \rightarrow c$ 。

因此可以建立一個有向圖，將每個字元 $a$ 看成一個節點，若 $a \rightarrow b$ 的花費為 $w$ ，則在節點 $a$ 和節點 $b$ 之間連一條權重為 $w$ 的邊。求出所有節點之間的最短路徑，即可得到答案。

由於題目只存在小寫英文數字，因此建圖時直接建 $26$ 個節點即可，並且將所有邊的權重初始化為 $+\infty$ ，表示不可連通。

需注意，由於可能存在重複的邊，因此在由 $original$ 和 $changed$ 建圖時，若兩個字元相同，則將邊的權重更新為最小值。

計算答案時，對於字串 $source$ 中的每個字元 $a$ ，若 $a \rightarrow b$ 的權重為 $+\infty$ ，則表示無法將 $a$ 轉換為 $b$ ，因此返回 $-1$ 。否則將所有權重相加即可。

複雜度分析

時間複雜度： $O(m+n+\Sigma^3)$ ，其中 $m$ 和 $n$ 分別為 $source$ 和 $cost$ 的長度， $\Sigma$ 為字元集合的大小，本題中為 $26$ 。
空間複雜度： $O(\Sigma^2)$ ，建立的圖的大小為 $\Sigma^2$ 。

class Solution:
    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
        g = [[float("inf")] * 26 for _ in range(26)]
        for i in range(26):
            g[i][i] = 0
        for u, v, w in zip(original, changed, cost): # 初始化
            u, v = ord(u)-ord('a'), ord(v)-ord('a')
            g[u][v] = min(g[u][v], w) # 這裡要注意，因為可能有重複的邊，所以要取最小值

        # Floyd-Warshall
        for k in range(26): # 枚舉中間點
            for i in range(26): # 枚舉起點
                if g[i][k] == float("inf"): continue # 不可能由 g[i][k] 轉移到其他點
                for j in range(26): # 枚舉終點
                    g[i][j] = min(g[i][j], g[i][k] + g[k][j]) # 更新 g[i][j]
        
        ans = 0
        for u, v in zip(source, target): # 枚舉每個字元
            u, v = ord(u)-ord('a'), ord(v)-ord('a')
            if g[u][v] == float("inf"): # 不連通，不可能修改成 target
                return -1
            ans += g[u][v] # 將 u 修改成 v 的成本加總
        return ans

class Solution {
public:
    long long minimumCost(string source, string target, vector<char>& original, vector<char>& changed, vector<int>& cost) {
        vector<vector<int>> g(26, vector<int>(26, INT_MAX/2)); // 初始化
        for (int i = 0; i < 26; i++) {
            g[i][i] = 0;
        }
        for (int i = 0; i < original.size(); i++) {
            int u = original[i] - 'a';
            int v = changed[i] - 'a';
            g[u][v] = min(g[u][v], cost[i]); // 這裡要注意，因為可能有重複的邊，所以要取最小值
        }
        // Floyd-Warshall
        for (int k = 0; k < 26; k++) { // 枚舉中間點
            for (int i = 0; i < 26; i++) { // 枚舉起點
                if (g[i][k] == INT_MAX/2) continue; // 不可能由 g[i][k] 轉移到其他點
                for (int j = 0; j < 26; j++) { // 枚舉終點
                    g[i][j] = min(g[i][j], g[i][k] + g[k][j]); // 更新 g[i][j]
                }
            }
        }

        long long ans = 0;
        for (int i = 0; i < source.size(); i++) { // 枚舉每個字元
            int u = source[i] - 'a';
            int v = target[i] - 'a';
            if (g[u][v] == INT_MAX/2) { // 不連通，不可能修改成 target
                return -1;
            }
            ans += g[u][v]; // 將 u 修改成 v 的成本加總
        }
        return ans;
    }
};