转换字符串的最小成本 II

标签: 图 字典树 数组 字符串 动态规划 最短路

难度: Hard

给你两个下标从 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] <= 106

Submission

运行时间: 768 ms

内存: 16.9 MB

class Solution:
    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
        dic = collections.defaultdict(set)
        dis = collections.defaultdict(lambda: collections.defaultdict(lambda: float('inf')))
        for s, t, c in zip(original, changed, cost):
            dic[len(s)].add(s)
            dic[len(t)].add(t)
            dis[s][s] = 0
            dis[t][t] = 0
            dis[s][t] = min(dis[s][t], c)
        
        for l in dic:
            for k in dic[l]:
                for i in dic[l]:
                    if i == k or dis[i][k] == float('inf'):
                        continue 
                    for j in dic[l]:
                        if i == j or j == k or dis[k][j] == float('inf'):
                            continue 
                        dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
        
        n = len(target)
        f = [float('inf')] * (n + 1)
        f[0] = 0
        for i in range(1, n + 1):
            if source[i - 1] == target[i - 1]:
                f[i] = f[i - 1]
            for l in dic:
                s, t = source[i - l : i], target[i - l : i]
                if s in dic[l] and t in dic[l]:
                    f[i] = min(f[i], f[i - l] + dis[s][t])
        return f[-1] if f[-1] != float('inf') else - 1

Explain

这道题目的核心思路是使用动态规划(DP)配合最短路径算法(Floyd-Warshall)来找到将source转换为target的最小成本。首先，建立一个字典dic来记录每个长度的original和changed子串，并用一个二维字典dis来记录从一个子串转换到另一个子串的最短代价。然后，使用Floyd-Warshall算法在同一长度的子串间更新最短路径的代价。接着，使用DP来求解，dp数组f[i]表示将source的前i个字符转换为target的前i个字符所需的最小成本。如果source和target在第i个字符上相同，则f[i]可以直接从f[i-1]转换而来。对于每个可能的转换长度l和相应的子串s和t，如果s和t都是有效的转换选项，那么可以尝试用dis[s][t]的代价来更新f[i]。最后，如果f[n]（n为字符串长度）不是无穷大，则返回f[n]，否则返回-1表示转换不可能。

时间复杂度: O(m + L^3 + nL)

空间复杂度: O(L^2 + n)

class Solution:
    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
        # 字典，记录各长度的子串
        dic = collections.defaultdict(set)
        # 记录最短转换成本的二维字典
        dis = collections.defaultdict(lambda: collections.defaultdict(lambda: float('inf')))
        # 建立初始的转换成本
        for s, t, c in zip(original, changed, cost):
            dic[len(s)].add(s)
            dic[len(t)].add(t)
            dis[s][s] = 0
            dis[t][t] = 0
            dis[s][t] = min(dis[s][t], c)
        # Floyd-Warshall算法更新最短路径
        for l in dic:
            for k in dic[l]:
                for i in dic[l]:
                    if i == k or dis[i][k] == float('inf'):
                        continue 
                    for j in dic[l]:
                        if i == j or j == k or dis[k][j] == float('inf'):
                            continue 
                        dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
        # DP数组
        n = len(target)
        f = [float('inf')] * (n + 1)
        f[0] = 0
        # 计算最小成本
        for i in range(1, n + 1):
            if source[i - 1] == target[i - 1]:
                f[i] = f[i - 1]
            for l in dic:
                s, t = source[i - l : i], target[i - l : i]
                if s in dic[l] and t in dic[l]:
                    f[i] = min(f[i], f[i - l] + dis[s][t])
        return f[-1] if f[-1] != float('inf') else - 1

Explore

在题解中，为了处理所有需要考虑的子串长度，算法首先通过遍历original和changed数组构建一个字典dic，该字典以子串的长度为键，对应长度的所有可能的子串为值。随后，在使用Floyd-Warshall算法时，只在具有相同长度的子串集合内执行更新，确保只比较和更新同等长度的子串之间的转换成本。这样通过对每个不同长度的子串集合分别运行Floyd-Warshall算法，可以确保所有需要考虑的子串长度都被正确处理。

Floyd-Warshall算法是一个经典的三层循环算法，用于计算图中所有节点对的最短路径。在处理字符串转换的最短成本时，算法通过初始化dis[s][t]为无穷大（除非有直接的转换成本），并且始终检查中间节点k的dis[i][k]和dis[k][j]是否为无穷大来避免无效的更新。这样，只有当存在有效的中间路径时，才会更新dis[i][j]。此外，算法本身的设计确保每个节点对(i,j)在考虑所有可能中间节点k后得出的结果是最优的，从而避免了循环依赖问题。

在动态规划的实现中，算法通过遍历所有可能的子串长度l，并对每个长度检查source和target中相应的子串s和t是否都存在于由Floyd-Warshall算法处理过的dic字典中。如果两个子串都存在且它们属于同一长度，那么会计算使用此转换的成本并尝试更新dp[i]。这种方法通过枚举所有有效的长度和对应的子串转换，确保考虑了所有可能的子串转换，从而为每个长度找到可能的最低转换成本。

当在动态规划中发现source和target在某个位置i的字符不相同时，算法不仅仅考虑直接从位置i-1到i的转换（如果字符相同），还会考虑所有可能的子串长度l，检查从i-l到i的子串s和t是否可以通过已知的转换成本进行转换。通过比较使用不同长度的子串转换所需的成本，选择最小的成本来更新dp数组的f[i]值。这种方式确保了即使单个字符不匹配，也能通过较长的子串转换来尝试找到总体的最小转换成本。