Hard
题目描述
给你两个长度为 n 的 0 索引字符串 source 和 target，两者都由小写英文字母组成。还给你两个 0 索引字符串数组 original 和 changed，以及一个整数数组 cost，其中 cost[i] 表示将字符串 original[i] 转换为字符串 changed[i] 的成本。
你从字符串 source 开始。在一次操作中，你可以从字符串中选择一个子字符串 x，并以成本 z 将其改为 y，如果存在任意索引 j 使得 cost[j] == z、original[j] == x 且 changed[j] == y。你可以进行任意次数的操作，但任意一对操作必须满足以下两个条件之一：
- 操作中选择的子字符串是
source[a..b]和source[c..d]，其中b < c或d < a。换句话说，两次操作中选择的索引是不相交的。 - 操作中选择的子字符串是
source[a..b]和source[c..d]，其中a == c且b == d。换句话说，两次操作中选择的索引是相同的。
使用任意次数的操作，返回将字符串 source 转换为字符串 target 的最小成本。如果无法将 source 转换为 target，则返回 -1。
示例 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
示例 2：
输入：source = "abcdefgh", target = "acdeeghh", original = ["bcd","fgh","thh"], changed = ["cde","thh","ghh"], cost = [1,3,5]
输出：9
示例 3：
输入：source = "abcdefgh", target = "addddddd", original = ["bcd","defgh"], changed = ["ddd","ddddd"], cost = [100,1578]
输出：-1
提示：
1 <= source.length == target.length <= 1000source, target只包含小写英文字母1 <= cost.length == original.length == changed.length <= 1001 <= original[i].length == changed[i].length <= source.lengthoriginal[i], changed[i]只包含小写英文字母original[i] != changed[i]1 <= cost[i] <= 10^6
解题思路
这是一个复杂的字符串转换问题，需要结合动态规划、图论和字符串匹配技术。
主要思路：
字符串映射与最短路径预处理：首先为所有出现在
original和changed中的唯一字符串分配ID，然后使用 Floyd-Warshall 算法计算任意两个字符串之间的最小转换成本。动态规划状态设计：定义
dp[i]表示将source的前i个字符转换为target对应前缀的最小成本。状态转移：对于每个位置
i，考虑两种情况：- 如果
source[i-1] == target[i-1]，则dp[i] = dp[i-1] - 枚举所有可能的子字符串
source[j..i-1]和对应的target[j..i-1]，如果存在转换路径，则更新dp[i] = min(dp[i], dp[j-1] + cost)
- 如果
字符串匹配优化：使用前缀树(Trie)或哈希表来快速检查某个子字符串是否可以进行转换。
算法流程：
- 构建字符串到ID的映射
- 用Floyd算法预计算所有字符串对之间的最短转换成本
- 使用动态规划计算最终答案
时间复杂度：O(m³ + n²)，其中m是唯一字符串数量，n是源字符串长度。 空间复杂度：O(m² + n)。
代码实现
class Solution {
public:
long long minimumCost(string source, string target, vector<string>& original, vector<string>& changed, vector<int>& cost) {
unordered_map<string, int> stringToId;
vector<string> idToString;
int nextId = 0;
// 分配字符串ID
auto getId = [&](const string& s) {
if (stringToId.find(s) == stringToId.end()) {
stringToId[s] = nextId++;
idToString.push_back(s);
}
return stringToId[s];
};
// 建图
for (int i = 0; i < original.size(); i++) {
getId(original[i]);
getId(changed[i]);
}
int m = nextId;
vector<vector<long long>> dist(m, vector<long long>(m, LLONG_MAX));
// 初始化距离
for (int i = 0; i < m; i++) {
dist[i][i] = 0;
}
for (int i = 0; i < original.size(); i++) {
int u = getId(original[i]);
int v = getId(changed[i]);
dist[u][v] = min(dist[u][v], (long long)cost[i]);
}
// Floyd算法
for (int k = 0; k < m; k++) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
if (dist[i][k] != LLONG_MAX && dist[k][j] != LLONG_MAX) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
int n = source.length();
vector<long long> dp(n + 1, LLONG_MAX);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
// 如果字符相同，无需转换
if (source[i-1] == target[i-1]) {
dp[i] = dp[i-1];
}
// 尝试所有可能的子字符串转换
for (int j = 0; j < i; j++) {
if (dp[j] == LLONG_MAX) continue;
string srcSub = source.substr(j, i - j);
string tgtSub = target.substr(j, i - j);
if (srcSub == tgtSub) {
dp[i] = min(dp[i], dp[j]);
} else if (stringToId.count(srcSub) && stringToId.count(tgtSub)) {
int srcId = stringToId[srcSub];
int tgtId = stringToId[tgtSub];
if (dist[srcId][tgtId] != LLONG_MAX) {
dp[i] = min(dp[i], dp[j] + dist[srcId][tgtId]);
}
}
}
}
return dp[n] == LLONG_MAX ? -1 : dp[n];
}
};
class Solution:
def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
from collections import defaultdict
# 分配字符串ID
string_to_id = {}
id_to_string = []
next_id = 0
def get_id(s):
nonlocal next_id
if s not in string_to_id:
string_to_id[s] = next_id
id_to_string.append(s)
next_id += 1
return string_to_id[s]
# 建图
for i in range(len(original)):
get_id(original[i])
get_id(changed[i])
m = next_id
dist = [[float('inf')] * m for _ in range(m)]
# 初始化距离
for i in range(m):
dist[i][i] = 0
for i in range(len(original)):
u = get_id(original[i])
v = get_id(changed[i])
dist[u][v] = min(dist[u][v], cost[i])
# Floyd算法
for k in range(m):
for i in range(m):
for j in range(m):
if dist[i][k] != float('inf') and dist[k][j] != float('inf'):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
n = len(source)
dp = [float('inf')] * (n + 1)
dp[0] = 0
for i in range(1, n + 1):
# 如果字符相同，无需转换
if source[i-1] == target[i-1]:
dp[i] = dp[i-1]
# 尝试所有可能的子字符串转换
for j in range(i):
if dp[j] == float('inf'):
continue
src_sub = source[j:i]
tgt_sub = target[j:i]
if src_sub == tgt_sub:
dp[i] = min(dp[i], dp[j])
elif src_sub in string_to_id and tgt_sub in string_to_id:
src_id = string_to_id[src_sub]
tgt_id = string_to_id[tgt_sub]
if dist[src_id][tgt_id] != float('inf'):
dp[i] = min(dp[i], dp[j] + dist[src_id][tgt_id])
return -1 if dp[n] == float('inf') else dp[n]
public class Solution {
public long MinimumCost(string source, string target, string[] original, string[] changed, int[] cost) {
var stringToId = new Dictionary<string, int>();
var idToString = new List<string>();
int nextId = 0;
int GetId(string s) {
if (!stringToId.ContainsKey(s)) {
stringToId[s] = nextId++;
idToString.Add(s);
}
return stringToId[s];
}
// 建图
for (int i = 0; i < original.Length; i++) {
GetId(original[i]);
GetId(changed[i]);
}
int m = nextId;
long[,] dist = new long[m, m];
// 初始化距离
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
dist[i, j] = i == j ? 0 : long.MaxValue;
}
}
for (int i = 0; i < original.Length; i++) {
int u = GetId(original[i]);
int v = GetId(changed[i]);
dist[u, v] = Math.Min(dist[u, v], cost[i]);
}
// Floyd算法
for (int k = 0; k < m; k++) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
if (dist[i, k] != long.MaxValue && dist[k, j] != long.MaxValue) {
dist[i, j] = Math.Min(dist[i, j], dist[i, k] + dist[k, j]);
}
}
}
}
int n = source.Length;
long[] dp = new long[n + 1];
for (int i = 0; i <= n; i++) {
dp[i] = long.MaxValue;
}
dp[0] = 0;
for (int i = 1; i <= n; i++) {
// 如果字符相同，无需转换
if (source[i-1] == target[i-1]) {
dp[i] = dp[i-1];
}
// 尝试所有可能的子字符串转换
for (int j = 0; j < i; j++) {
if (dp[j] == long.MaxValue) continue;
string srcSub = source.Substring(j, i - j);
string tgtSub = target.Substring(j, i - j);
if (srcSub == tgtSub) {
dp[i] = Math.Min(dp[i], dp[j]);
} else if (stringToId.ContainsKey(srcSub) && stringToId.ContainsKey(tgtSub)) {
int srcId = stringToId[srcSub];
int tgtId = stringToId[tgtSub];
if (dist[srcId, tgtId] != long.MaxValue) {
dp[i] = Math.Min(dp[i], dp[j] + dist[srcId, tgtId]);
}
}
}
}
return dp[n] == long.MaxValue ? -1 : dp[n];
}
}
var minimumCost = function(source, target, original, changed, cost) {
const stringToId = new Map();
const idToString = [];
let nextId = 0;
const getId = (s) => {
if (!stringToId.has(s)) {
stringToId.set(s, nextId++);
idToString.push(s);
}
return stringToId.get(s);
};
// 建图
for (let i = 0; i < original.length; i++) {
getId(original[i]);
getId(changed[i]);
}
复杂度分析
| 指标 | 复杂度 |
|---|---|
| 时间 | - |
| 空间 | - |