题目

给你两个下标从 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[a..b] 和 source[c..d] ，满足 b < c  或 d < a 。换句话说，两次操作中选择的下标 不相交 。
• 在两次操作中选择的子串分别是 source[a..b] 和 source[c..d] ，满足 a == c 且 b == d 。换句话说，两次操作中选择的下标 相同 。

返回将字符串 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"，执行以下操作：

• 将子串 source[1..1] 从 "b" 改为 "c" ，成本为 5 。
• 将子串 source[2..2] 从 "c" 改为 "e" ，成本为 1 。
• 将子串 source[2..2] 从 "e" 改为 "b" ，成本为 2 。
• 将子串 source[3..3] 从 "d" 改为 "e" ，成本为 20 。 产生的总成本是 5 + 1 + 2 + 20 = 28 。 可以证明这是可能的最小成本。

示例 2：

输入：source = "abcdefgh", target = "acdeeghh", original = ["bcd","fgh","thh"], changed = ["cde","thh","ghh"], cost = [1,3,5] 输出：9 解释：将 "abcdefgh" 转换为 "acdeeghh"，执行以下操作：

• 将子串 source[1..3] 从 "bcd" 改为 "cde" ，成本为 1 。
• 将子串 source[5..7] 从 "fgh" 改为 "thh" ，成本为 3 。可以执行此操作，因为下标 [5,7] 与第一次操作选中的下标不相交。
• 将子串 source[5..7] 从 "thh" 改为 "ghh" ，成本为 5 。可以执行此操作，因为下标 [5,7] 与第一次操作选中的下标不相交，且与第二次操作选中的下标相同。 产生的总成本是 1 + 3 + 5 = 9 。 可以证明这是可能的最小成本。

示例 3：

输入：source = "abcdefgh", target = "addddddd", original = ["bcd","defgh"], changed = ["ddd","ddddd"], cost = [100,1578] 输出：-1 解释：无法将 "abcdefgh" 转换为 "addddddd" 。 如果选择子串 source[1..3] 执行第一次操作，以将 "abcdefgh" 改为 "adddefgh" ，你无法选择子串 source[3..7] 执行第二次操作，因为两次操作有一个共用下标 3 。 如果选择子串 source[3..7] 执行第一次操作，以将 "abcdefgh" 改为 "abcddddd" ，你无法选择子串 source[1..3] 执行第二次操作，因为两次操作有一个共用下标 3 。

提示：

• 1 <= source.length == target.length <= 1000
• source、target 均由小写英文字母组成
• 1 <= cost.length == original.length == changed.length <= 100
• 1 <= original[i].length == changed[i].length <= source.length
• original[i]、changed[i] 均由小写英文字母组成
• original[i] != changed[i]
• 1 <= cost[i] <= 10^6

解题思路

这道题的难点在于操作规则：

1. 子串替换：不是简单的字符替换，而是变长字符串的替换。
2. 不相交或相同：这意味着我们不能进行“部分重叠”的操作。例如，不能先改 index[0..5]，再改 index[4..8]。这实际上暗示了这是一个**划分（Partition）**问题——我们需要将 source 字符串切分成若干段，每一段要么本来就和 target 相同，要么可以通过一系列操作变成 target 的对应段。
3. 多次操作（相同下标）：意味着如果我有规则 A -> B 和 B -> C，我可以把子串 A 变成 C。这暗示了传递性，即图论中的最短路径。

第一步：数据预处理与图建模（Floyd-Warshall）

由于我们可以对同一个子串位置进行多次操作（例如 abc -> def -> ghi），我们需要预处理出所有可能的子串转换的最小成本。

1. 离散化（映射 ID）：
   • original 和 changed 数组中的字符串就是图中的节点。
   • 将所有出现过的字符串去重，映射为整数 ID（$0, 1, 2, \dots, m-1$）。
   • 注意：最多只有 $100$ 组规则，所以唯一字符串的数量 $m$ 最多为 $200$。这是一个很小的图。
2. 构建邻接矩阵：
   • 初始化一个 $m \times m$ 的矩阵 dist，dist[i][j] 初始化为无穷大，dist[i][i] = 0。
   • 根据 cost 数组填充矩阵：dist[id(original[k])][id(changed[k])] = min(当前值, cost[k])。
3. 计算全源最短路：
   • 使用 Floyd-Warshall 算法。因为节点数 $m \le 200$，复杂度 $O(m^3)$ 约为 $8 \times 10^6$，完全可以接受。
   • 计算完成后，dist[u][v] 就代表将字符串 $u$ 转换为字符串 $v$ 所需的最小总成本（考虑了所有中间步骤）。

第二步：线性动态规划（Linear DP）

现在问题转化为了：将 source 分割成若干段，每一段转换的代价之和最小。

• 定义状态：dp[i] 表示将 source 的前 $i$ 个字符（source[0...i-1]）转换为 target 的前 $i$ 个字符所需的最小成本。
• 初始化：dp[0] = 0，其余为无穷大。
• 状态转移：对于当前的索引 $i$（也就是我们已经处理好了前 $i$ 个字符，现在考虑从 $i$ 开始的一段）：
  1. 直接匹配（无需修改）：如果 source[i] == target[i]，我们可以直接跳过这个字符，不需要花费额外成本。
     • dp[i+1] = min(dp[i+1], dp[i])
  2. 子串替换：尝试匹配所有可能的子串长度 len。
     • 令 j = i + len。
     • 提取子串 sub_src = source[i:j] 和 sub_dst = target[i:j]。
     • 如果 sub_src 和 sub_dst 都在我们的节点映射表中，并且它们之间存在通路（即 dist[id(sub_src)][id(sub_dst)] != inf）：
     • dp[j] = min(dp[j], dp[i] + dist[id(sub_src)][id(sub_dst)])
• 优化技巧：
  • 不要遍历所有可能的长度（1 到 $n$）。只遍历规则中出现过的长度。用一个集合 valid_lengths 存储 original 中所有字符串的长度。
  • 这样内层循环的次数就大大减少了。

复杂度分析

• $N$: source 和 target 的长度 ($N \le 1000$)。
• $K$: 转换规则的数量，即 original 的长度 ($K \le 100$)。
• $M$: 参与转换的唯一字符串的数量。最坏情况下 $M = 2K$ (即 $original$ 和 $changed$ 无交集且内部无重复)，所以 $M \le 200$。
• $L$: 转换规则中字符串的平均长度 ($L \le N$)。
• $|Lens|$: original 中不同长度的种类数 ($|Lens| \le K$)。

时间复杂度

预处理 (图建摸 + Floyd-Warshall)

1. 字符串映射与建图：需要遍历所有规则字符串进行哈希和去重。
   • 复杂度：$O(K \cdot L)$。
2. Floyd-Warshall 算法：这是计算全源最短路的核心瓶颈。
   • 复杂度：$O(M^3)$。
   • 代入数值：$200^3 = 8,000,000$。对于现代 CPU (通常 $10^8$ ops/sec)，这大约耗时 80ms - 100ms，是可以接受的常量开销。

线性动态规划 (Linear DP)

DP 的状态转移方程是：

$$dp[j] = \min(dp[j], dp[i] + \text{cost})$$

代码结构为两层循环：外层遍历位置 $i$，内层遍历可能的长度 $len$。

1. 外层循环：遍历 $0$ 到 $N$，共 $N$ 次。
2. 内层循环：遍历 possible_lens 集合，最坏情况有 $K$ 种长度。
3. 循环体操作：
   • 字符串切片 (Slicing)：Python 中 source[i:i+len] 需要 $O(len)$ 的时间。
   • 哈希查找 (Hashing)：将切片后的字符串在 str_to_id 中查找，平均 $O(len)$。
   • 查表：dist[u][v] 是 $O(1)$。
   • 单次内部操作总耗时：$O(L)$。

DP 总复杂度：$O(N \cdot |Lens| \cdot L)$

最坏情况下（虽然很少见），$|Lens| \approx K$，且 $L$ 较大，则为 $O(N \cdot K \cdot L)$。

总时间复杂度

$$O(M^3 + N \cdot K \cdot L)$$

空间复杂度

1. 距离矩阵 (dist)：存储 $M \times M$ 的图。
   • 空间：$O(M^2)$。($200 \times 200 = 40,000$ int，非常小)。
2. DP 数组：长度为 $N$。
   • 空间：$O(N)$。
3. 哈希映射 (str_to_id)：存储所有唯一字符串。
   • 空间：$O(K \cdot L)$ (存储字符本身)。

总空间复杂度：

$$O(M^2 + N + K \cdot L)$$

具体代码

class Solution:
    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
        n = len(source)
        
        # --- 步骤 1: 图建模与离散化 ---
        # 将所有涉及的字符串映射为唯一的整数 ID，便于构建邻接矩阵
        all_strs = set(original) | set(changed)
        str_to_id = {s: i for i, s in enumerate(all_strs)}
        m = len(all_strs)
        
        # 初始化距离矩阵 (m x m)
        inf = float('inf')
        dist = [[inf] * m for _ in range(m)]
        for i in range(m):
            dist[i][i] = 0
            
        # 填充初始边权重 (取最小值，因为可能存在多条规则对应同一对字符串)
        for u, v, c in zip(original, changed, cost):
            u_id = str_to_id[u]
            v_id = str_to_id[v]
            dist[u_id][v_id] = min(dist[u_id][v_id], c)
            
        # --- 步骤 2: Floyd-Warshall 算法预处理 ---
        # 计算所有节点对之间的最短路径，处理传递性 (A->B->C)
        # 复杂度 O(m^3)，m <= 200，计算量约 8e6，完全可接受
        for k in range(m):
            for i in range(m):
                if dist[i][k] == inf: continue # 剪枝优化
                for j in range(m):
                    if dist[k][j] != inf:
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        
        # 优化技巧：只遍历 original 中出现过的长度，减少 DP 内层循环次数
        possible_lens = set(len(s) for s in original)
        
        # --- 步骤 3: 线性动态规划 (Linear DP) ---
        # dp[i] 表示将 source[:i] 转换为 target[:i] 的最小成本
        dp = [inf] * (n + 1)
        dp[0] = 0
        
        for i in range(n):
            if dp[i] == inf:
                continue
            
            # 策略 A: 字符相等，直接跳过 (Cost = 0)
            if source[i] == target[i]:
                dp[i + 1] = min(dp[i + 1], dp[i])
            
            # 策略 B: 子串替换 (Cost = dist[sub_src][sub_tgt])
            for length in possible_lens:
                j = i + length
                if j > n:
                    continue
                
                sub_src = source[i:j]
                sub_tgt = target[i:j]
                
                # 必须两个子串都在规则图中，才有可能存在转换路径
                if sub_src in str_to_id and sub_tgt in str_to_id:
                    u_id = str_to_id[sub_src]
                    v_id = str_to_id[sub_tgt]
                    
                    if dist[u_id][v_id] != inf:
                        dp[j] = min(dp[j], dp[i] + dist[u_id][v_id])
                        
        return dp[n] if dp[n] != inf else -1