Medium

题目描述

给你两个下标从 0 开始的字符串 source 和 target，它们的长度均为 n 并且由小写英文字母组成。另给你两个下标从 0 开始的字符数组 original 和 changed，以及一个整数数组 cost，其中 cost[i] 代表将字符 original[i] 更改为字符 changed[i] 的代价。

你从字符串 source 开始。在一次操作中，如果存在 任意 下标 j 满足 cost[j] == z、original[j] == x 以及 changed[j] == y，你就可以选择字符串中的一个字符 x 并以 z 的代价将其更改为字符 y。

返回将字符串 source 转换为字符串 target 所需的 最小 代价。如果不可能完成转换，则返回 -1。

注意，可能存在下标 i、j 使得 original[j] == original[i] 且 changed[j] == changed[i]。

示例 1：

输入：source = "abcd", target = "acbe", original = ["a","b","c","c","e","d"], changed = ["b","c","b","e","b","e"], cost = [2,5,5,1,2,20]
输出：28
解释：将字符串 "abcd" 转换为字符串 "acbe"：
- 将下标 1 处的值从 'b' 更改为 'c'，代价为 5
- 将下标 2 处的值从 'c' 更改为 'e'，代价为 1  
- 将下标 2 处的值从 'e' 更改为 'b'，代价为 2
- 将下标 3 处的值从 'd' 更改为 'e'，代价为 20
总代价为 5 + 1 + 2 + 20 = 28

示例 2：

输入：source = "aaaa", target = "bbbb", original = ["a","c"], changed = ["c","b"], cost = [1,2]
输出：12
解释：要将字符 'a' 更改为 'b'，需要先将 'a' 更改为 'c'（代价为1），再将 'c' 更改为 'b'（代价为2），总代价为3。将所有 'a' 都更改为 'b' 的总代价为 3 * 4 = 12。

约束条件：

  • 1 <= source.length == target.length <= 10^5
  • source, target 由小写英文字母组成
  • 1 <= cost.length == original.length == changed.length <= 2000
  • original[i], changed[i] 是小写英文字母
  • 1 <= cost[i] <= 10^6
  • original[i] != changed[i]

解题思路

这道题本质上是一个图论最短路径问题。我们需要找到从每个字符到另一个字符的最小转换代价。

解题思路：

  1. 建图阶段：将26个小写字母看作图中的节点，每个转换规则 (original[i], changed[i], cost[i]) 看作一条有向边，权重为 cost[i]。如果存在多条相同的边，保留权重最小的那条。

  2. 最短路径计算：由于只有26个节点，我们可以使用 Floyd-Warshall 算法 预计算所有字符对之间的最短路径。这比对每个字符对单独使用 Dijkstra 算法更高效。

  3. 计算总代价：遍历 source 和 target 的每一位，如果字符相同则代价为0；否则查找预计算的最短路径。如果某个转换不可达，返回-1。

算法优势：

  • Floyd-Warshall 的时间复杂度为 O(26³)，常数级别
  • 预计算后查询时间为 O(1)
  • 空间复杂度 O(26²)，也是常数级别

这种方法特别适合本题，因为字符集固定为26个小写字母，预计算的开销很小，但可以高效处理长字符串的查询。

代码实现

class Solution {
public:
    long long minimumCost(string source, string target, vector<char>& original, vector<char>& changed, vector<int>& cost) {
        const int INF = 1e9;
        vector<vector<int>> dist(26, vector<int>(26, INF));
        
        // 初始化距离矩阵
        for (int i = 0; i < 26; i++) {
            dist[i][i] = 0;
        }
        
        // 建图
        for (int i = 0; i < cost.size(); i++) {
            int from = original[i] - 'a';
            int to = changed[i] - 'a';
            dist[from][to] = min(dist[from][to], cost[i]);
        }
        
        // Floyd-Warshall算法
        for (int k = 0; k < 26; k++) {
            for (int i = 0; i < 26; i++) {
                for (int j = 0; j < 26; j++) {
                    if (dist[i][k] != INF && dist[k][j] != INF) {
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }
        
        // 计算总代价
        long long totalCost = 0;
        for (int i = 0; i < source.length(); i++) {
            int from = source[i] - 'a';
            int to = target[i] - 'a';
            if (dist[from][to] == INF) {
                return -1;
            }
            totalCost += dist[from][to];
        }
        
        return totalCost;
    }
};

class Solution:
    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
        INF = float('inf')
        dist = [[INF] * 26 for _ in range(26)]
        
        # 初始化距离矩阵
        for i in range(26):
            dist[i][i] = 0
        
        # 建图
        for i in range(len(cost)):
            from_char = ord(original[i]) - ord('a')
            to_char = ord(changed[i]) - ord('a')
            dist[from_char][to_char] = min(dist[from_char][to_char], cost[i])
        
        # Floyd-Warshall算法
        for k in range(26):
            for i in range(26):
                for j in range(26):
                    if dist[i][k] != INF and dist[k][j] != INF:
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        
        # 计算总代价
        total_cost = 0
        for i in range(len(source)):
            from_char = ord(source[i]) - ord('a')
            to_char = ord(target[i]) - ord('a')
            if dist[from_char][to_char] == INF:
                return -1
            total_cost += dist[from_char][to_char]
        
        return total_cost

public class Solution {
    public long MinimumCost(string source, string target, char[] original, char[] changed, int[] cost) {
        const int INF = 1000000000;
        int[,] dist = new int[26, 26];
        
        // 初始化距离矩阵
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                dist[i, j] = i == j ? 0 : INF;
            }
        }
        
        // 建图
        for (int i = 0; i < cost.Length; i++) {
            int from = original[i] - 'a';
            int to = changed[i] - 'a';
            dist[from, to] = Math.Min(dist[from, to], cost[i]);
        }
        
        // Floyd-Warshall算法
        for (int k = 0; k < 26; k++) {
            for (int i = 0; i < 26; i++) {
                for (int j = 0; j < 26; j++) {
                    if (dist[i, k] != INF && dist[k, j] != INF) {
                        dist[i, j] = Math.Min(dist[i, j], dist[i, k] + dist[k, j]);
                    }
                }
            }
        }
        
        // 计算总代价
        long totalCost = 0;
        for (int i = 0; i < source.Length; i++) {
            int from = source[i] - 'a';
            int to = target[i] - 'a';
            if (dist[from, to] == INF) {
                return -1;
            }
            totalCost += dist[from, to];
        }
        
        return totalCost;
    }
}

var minimumCost = function(source, target, original, changed, cost) {
    const INF = 1e9;
    const dist = Array(26).fill(null).map(() => Array(26).fill(INF));
    
    // 初始化距离矩阵
    for (let i = 0; i < 26; i++) {
        dist[i][i] = 0;
    }
    
    // 建图
    for (let i = 0; i < cost.length; i++) {
        const from = original[i].charCodeAt(0) - 'a'.charCodeAt(0);
        const to = changed[i].charCodeAt(0) - 'a'.charCodeAt(0);
        dist[from][to] = Math.min(dist[from][to], cost[i]);
    }
    
    // Floyd-Warshall算法
    for (let k = 0; k < 26; k++) {
        for (let i = 0; i < 26; i++) {
            for (let j = 0; j < 26; j++) {
                if (dist[i][k] !== INF && dist[k][j] !== INF) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
    
    // 计算总代价
    let totalCost = 0;
    for (let i = 0; i < source.length; i++) {
        const from = source[i].charCodeAt(0) - 'a'.charCodeAt(0);
        const to = target[i].charCodeAt(0) - 'a'.charCodeAt(0);
        if (dist[from][to]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(26³ + m + n)，其中 m 是转换规则数量，n 是字符串长度。Floyd-Warshall 算法为 O(26³)，建图为 O(m)，计算答案为 O(n)
空间复杂度O(26²) = O(1)，使用 26×26 的距离矩阵存储所有字符对的最短路径

相关题目