转换字符串的最小成本 II

You are given two 0-indexed strings source and target, both of length n and consisting of lowercase English characters. You are also given two 0-indexed string arrays original and changed, and an integer array cost, where cost[i] represents the cost of converting the string original[i] to the string changed[i].

You start with the string source. In one operation, you can pick a substring x from the string, and change it to y at a cost of z if there exists any index j such that cost[j] == z, original[j] == x, and changed[j] == y. You are allowed to do any number of operations, but any pair of operations must satisfy either of these two conditions:

• The substrings picked in the operations are source[a..b] and source[c..d] with either b < c or d < a. In other words, the indices picked in both operations are disjoint.
• The substrings picked in the operations are source[a..b] and source[c..d] with a == c and b == d. In other words, the indices picked in both operations are identical.

Return the minimum cost to convert the string source to the string target using any number of operations. If it is impossible to convert source to target, return -1.

Note that there may exist indices i, j such that original[j] == original[i] and changed[j] == changed[i].

 

Example 1:

Input: 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]
Output: 28
Explanation: To convert "abcd" to "acbe", do the following operations:
- Change substring source[1..1] from "b" to "c" at a cost of 5.
- Change substring source[2..2] from "c" to "e" at a cost of 1.
- Change substring source[2..2] from "e" to "b" at a cost of 2.
- Change substring source[3..3] from "d" to "e" at a cost of 20.
The total cost incurred is 5 + 1 + 2 + 20 = 28. 
It can be shown that this is the minimum possible cost.

Example 2:

Input: source = "abcdefgh", target = "acdeeghh", original = ["bcd","fgh","thh"], changed = ["cde","thh","ghh"], cost = [1,3,5]
Output: 9
Explanation: To convert "abcdefgh" to "acdeeghh", do the following operations:
- Change substring source[1..3] from "bcd" to "cde" at a cost of 1.
- Change substring source[5..7] from "fgh" to "thh" at a cost of 3. We can do this operation because indices [5,7] are disjoint with indices picked in the first operation.
- Change substring source[5..7] from "thh" to "ghh" at a cost of 5. We can do this operation because indices [5,7] are disjoint with indices picked in the first operation, and identical with indices picked in the second operation.
The total cost incurred is 1 + 3 + 5 = 9.
It can be shown that this is the minimum possible cost.

Example 3:

Input: source = "abcdefgh", target = "addddddd", original = ["bcd","defgh"], changed = ["ddd","ddddd"], cost = [100,1578]
Output: -1
Explanation: It is impossible to convert "abcdefgh" to "addddddd".
If you select substring source[1..3] as the first operation to change "abcdefgh" to "adddefgh", you cannot select substring source[3..7] as the second operation because it has a common index, 3, with the first operation.
If you select substring source[3..7] as the first operation to change "abcdefgh" to "abcddddd", you cannot select substring source[1..3] as the second operation because it has a common index, 3, with the first operation.

 

Constraints:

• 1 <= source.length == target.length <= 1000
• source, target consist only of lowercase English characters.
• 1 <= cost.length == original.length == changed.length <= 100
• 1 <= original[i].length == changed[i].length <= source.length
• original[i], changed[i] consist only of lowercase English characters.
• original[i] != changed[i]
• 1 <= cost[i] <= 106

// Java Stream Solution
// 思路：类似于传统的Java解决方案，但使用Java Streams来处理数组的操作。

import java.util.*;
import java.util.stream.*;

public class SolutionStream {
    public int minCost(String source, String target, String[] original, String[] changed, int[] cost) {
        int n = source.length();
        int[][] dp = new int[n + 1][n + 1];
        Arrays.stream(dp).forEach(row -> Arrays.fill(row, Integer.MAX_VALUE));
        dp[0][0] = 0;
        IntStream.rangeClosed(0, n).forEach(i -> {
            IntStream.rangeClosed(0, n).forEach(j -> {
                if (dp[i][j] == Integer.MAX_VALUE) return;
                if (i < n && source.charAt(i) == target.charAt(j)) dp[i + 1][j + 1] = Math.min(dp[i + 1][j + 1], dp[i][j]);
                IntStream.range(0, original.length).forEach(k -> {
                    String orig = original[k], chng = changed[k];
                    int len = orig.length();
                    if (i + len <= n && j + len <= n && source.substring(i, i + len).equals(orig) && target.substring(j, j + len).equals(chng)) {
                        dp[i + len][j + len] = Math.min(dp[i + len][j + len], dp[i][j] + cost[k]);
                    }
                });
            });
        });
        return dp[n][n] == Integer.MAX_VALUE ? -1 : dp[n][n];
    }
}

这道题目的核心思路是使用动态规划(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)