MediumRating 1882
2976. Minimum Cost to Convert String I
arraystringgraphshortest-path
解題說明
Minimum Cost to Convert String I
題目描述：給定兩個等長字串 source 和 target（僅含小寫英文字母），以及三個陣列 original、changed、cost，表示可以花費 cost[i] 將字元 original[i] 轉換為 changed[i]。求將 source 轉換為 target 的最小總花費，若不可能則回傳 -1。
解題思路：由於字元只有 26 個小寫英文字母，可以建立一個 26×26 的最短路徑矩陣。將每個轉換規則視為有向邊，使用 Floyd-Warshall 演算法求出任意兩字元間的最小轉換成本。接著遍歷字串，將每個位置 source[i] -> target[i] 的最短路徑成本加總即可。若任一位置的轉換不可達，回傳 -1。
C++ 解法
複雜度分析
時間複雜度：O(26³ + n) — Floyd-Warshall 在 26 個字元上為常數時間，遍歷字串為 O(n)。
空間複雜度：O(26²) = O(1) — 距離矩陣大小固定為 26×26。
虛擬碼
1. Initialize 26x26 distance matrix with INF, dist[i][i] = 0 2. For each conversion rule (original[i], changed[i], cost[i]): a. dist[original[i]][changed[i]] = min(current, cost[i]) 3. Run Floyd-Warshall: for k, i, j in [0,25]: a. dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 4. For each position i in source: a. If source[i] != target[i], add dist[source[i]][target[i]] to answer b. If distance is INF, return -1 5. Return total answer
其他解法
Dijkstra 多源最短路 O(26 × (E + 26 log 26))：對 26 個起點各跑一次 Dijkstra。邊數可能重複，但頂點數固定為 26，效率相當。對於稀疏圖（邊少時）可能比 Floyd-Warshall 快，但實作更複雜且在此題規模下無明顯優勢。
BFS O(26 × (26 + E))：若所有邊權為 1 可用 BFS，但此題有不同權重，需使用加權最短路演算法。
延伸思考
- 如果字元不限於小寫字母而是任意 Unicode 字元，Floyd-Warshall 還適用嗎？該如何處理？
- 如果允許同時將連續子字串進行轉換（batch conversion），問題會如何變化？（參見 Part II）
- 如果轉換規則可以串聯但有次數限制，該怎麼建模？