class Solution {
public:
long long minimumCost(string source, string target, vector<string>& original, vector<string>& changed, vector<int>& cost) {
}
};
100158. 转换字符串的最小成本 II
给你两个下标从 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 <= 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] <= 106原站题解
cpp 解法, 执行用时: 496 ms, 内存消耗: 361.2 MB, 提交时间: 2023-12-25 00:40:53
struct Node {
Node *son[26]{};
int sid = -1; // 字符串的编号
};
class Solution {
public:
long long
minimumCost(string source, string target, vector<string> &original, vector<string> &changed, vector<int> &cost) {
Node *root = new Node();
int sid = 0;
auto put = [&](string &s) -> int {
Node *o = root;
for (char b: s) {
int i = b - 'a';
if (o->son[i] == nullptr) {
o->son[i] = new Node();
}
o = o->son[i];
}
if (o->sid < 0) {
o->sid = sid++;
}
return o->sid;
};
// 初始化距离矩阵
int m = cost.size();
vector<vector<int>> dis(m * 2, vector<int>(m * 2, INT_MAX / 2));
for (int i = 0; i < m * 2; i++) {
dis[i][i] = 0;
}
for (int i = 0; i < m; i++) {
int x = put(original[i]);
int y = put(changed[i]);
dis[x][y] = min(dis[x][y], cost[i]);
}
// Floyd 求任意两点最短路
for (int k = 0; k < sid; k++) {
for (int i = 0; i < sid; i++) {
if (dis[i][k] == INT_MAX / 2) { // 加上这句话，巨大优化！
continue;
}
for (int j = 0; j < sid; j++) {
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
int n = source.size();
vector<long long> f(n + 1);
for (int i = n - 1; i >= 0; i--) {
// 不修改 source[i]
f[i] = source[i] == target[i] ? f[i + 1] : LONG_LONG_MAX / 2;
Node *p = root, *q = root;
for (int j = i; j < n; j++) {
p = p->son[source[j] - 'a'];
q = q->son[target[j] - 'a'];
if (p == nullptr || q == nullptr) {
break;
}
if (p->sid < 0 || q->sid < 0) {
continue;
}
// 修改从 i 到 j 的这一段
int d = dis[p->sid][q->sid];
if (d < INT_MAX / 2) {
f[i] = min(f[i], dis[p->sid][q->sid] + f[j + 1]);
}
}
}
return f[0] < LONG_LONG_MAX / 2 ? f[0] : -1;
}
};
java 解法, 执行用时: 142 ms, 内存消耗: 44.9 MB, 提交时间: 2023-12-25 00:40:42
class Node {
Node[] son = new Node[26];
int sid = -1; // 字符串的编号
}
class Solution {
private Node root = new Node();
private int sid = 0;
public long minimumCost(String source, String target, String[] original, String[] changed, int[] cost) {
// 初始化距离矩阵
int m = cost.length;
int[][] dis = new int[m * 2][m * 2];
for (int i = 0; i < dis.length; i++) {
Arrays.fill(dis[i], Integer.MAX_VALUE / 2);
dis[i][i] = 0;
}
for (int i = 0; i < cost.length; i++) {
int x = put(original[i]);
int y = put(changed[i]);
dis[x][y] = Math.min(dis[x][y], cost[i]);
}
// Floyd 求任意两点最短路
for (int k = 0; k < sid; k++) {
for (int i = 0; i < sid; i++) {
if (dis[i][k] == Integer.MAX_VALUE / 2) {
continue;
}
for (int j = 0; j < sid; j++) {
dis[i][j] = Math.min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
char[] s = source.toCharArray();
char[] t = target.toCharArray();
int n = s.length;
long[] f = new long[n + 1];
for (int i = n - 1; i >= 0; i--) {
// 不修改 source[i]
f[i] = s[i] == t[i] ? f[i + 1] : Long.MAX_VALUE / 2;
Node p = root, q = root;
for (int j = i; j < n; j++) {
p = p.son[s[j] - 'a'];
q = q.son[t[j] - 'a'];
if (p == null || q == null) {
break;
}
if (p.sid < 0 || q.sid < 0) {
continue;
}
// 修改从 i 到 j 的这一段
int d = dis[p.sid][q.sid];
if (d < Integer.MAX_VALUE / 2) {
f[i] = Math.min(f[i], d + f[j + 1]);
}
}
}
return f[0] < Long.MAX_VALUE / 2 ? f[0] : -1;
}
private int put(String s) {
Node o = root;
for (char b : s.toCharArray()) {
int i = b - 'a';
if (o.son[i] == null) {
o.son[i] = new Node();
}
o = o.son[i];
}
if (o.sid < 0) {
o.sid = sid++;
}
return o.sid;
}
}
python3 解法, 执行用时: 3156 ms, 内存消耗: 19.2 MB, 提交时间: 2023-12-25 00:40:13
class Node:
__slots__ = 'son', 'sid'
def __init__(self):
self.son = [None] * 26
self.sid = -1 # 字符串的编号
class Solution:
def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
ord_a = ord('a')
root = Node()
sid = 0
def put(s: str) -> int:
o = root
for c in s:
i = ord(c) - ord_a
if o.son[i] is None:
o.son[i] = Node()
o = o.son[i]
if o.sid < 0:
nonlocal sid
o.sid = sid
sid += 1
return o.sid
# 初始化距离矩阵
m = len(cost)
dis = [[inf] * (m * 2) for _ in range(m * 2)]
for x, y, c in zip(original, changed, cost):
x = put(x)
y = put(y)
dis[x][y] = min(dis[x][y], c)
# Floyd 求任意两点最短路
for k in range(sid):
for i in range(sid):
if dis[i][k] == inf: # 加上这句话，巨大优化！
continue
for j in range(sid):
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
n = len(source)
f = [inf] * n + [0]
for i in range(n - 1, -1, -1):
if source[i] == target[i]:
f[i] = f[i + 1] # 不修改 source[i]
p, q = root, root
for j in range(i, n):
p = p.son[ord(source[j]) - ord_a]
q = q.son[ord(target[j]) - ord_a]
if p is None or q is None:
break
if p.sid < 0 or q.sid < 0:
continue
# 修改从 i 到 j 的这一段
f[i] = min(f[i], dis[p.sid][q.sid] + f[j + 1])
return f[0] if f[0] < inf else -1
python3 解法, 执行用时: 836 ms, 内存消耗: 17.7 MB, 提交时间: 2023-12-25 00:40:06
class Solution:
def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
len_to_strs = defaultdict(set)
dis = defaultdict(lambda: defaultdict(lambda: inf))
for x, y, c in zip(original, changed, cost):
len_to_strs[len(x)].add(x) # 按照长度分组
len_to_strs[len(y)].add(y)
dis[x][y] = min(dis[x][y], c)
dis[x][x] = 0
dis[y][y] = 0
# 不同长度的字符串必然在不同的连通块中，分别计算 Floyd
for strs in len_to_strs.values():
for k in strs:
for i in strs:
if dis[i][k] == inf: # 加上这句话，巨大优化！
continue
for j in strs:
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
# f[i] 表示把 source[:i] 变成 target[:i] 的最小成本
n = len(source)
f = [0] + [inf] * n
for i in range(1, n + 1):
if source[i - 1] == target[i - 1]:
f[i] = f[i - 1] # 不修改 source[i]
for size, strs in len_to_strs.items(): # 枚举子串长度
if i < size:
continue
s = source[i - size: i]
t = target[i - size: i]
if s in strs and t in strs: # 可以替换
f[i] = min(f[i], dis[s][t] + f[i - size])
return f[n] if f[n] < inf else -1
golang 解法, 执行用时: 208 ms, 内存消耗: 8.8 MB, 提交时间: 2023-12-25 00:39:37
func minimumCost(source, target string, original, changed []string, cost []int) int64 {
const inf = math.MaxInt / 2
type node struct {
son [26]*node
sid int // 字符串的编号
}
root := &node{}
sid := 0
put := func(s string) int {
o := root
for _, b := range s {
b -= 'a'
if o.son[b] == nil {
o.son[b] = &node{sid: -1}
}
o = o.son[b]
}
if o.sid < 0 {
o.sid = sid
sid++
}
return o.sid
}
// 初始化距离矩阵
m := len(cost)
dis := make([][]int, m*2)
for i := range dis {
dis[i] = make([]int, m*2)
for j := range dis[i] {
if j != i {
dis[i][j] = inf
}
}
}
for i, c := range cost {
x := put(original[i])
y := put(changed[i])
dis[x][y] = min(dis[x][y], c)
}
// Floyd 求任意两点最短路
for k := 0; k < sid; k++ {
for i := 0; i < sid; i++ {
if dis[i][k] == inf {
continue
}
for j := 0; j < sid; j++ {
dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j])
}
}
}
n := len(source)
memo := make([]int, n)
for i := range memo {
memo[i] = -1
}
var dfs func(int) int
dfs = func(i int) int {
if i >= n {
return 0
}
ptr := &memo[i]
if *ptr != -1 {
return *ptr
}
res := inf
if source[i] == target[i] {
res = dfs(i + 1) // 不修改 source[i]
}
p, q := root, root
for j := i; j < n; j++ {
p = p.son[source[j]-'a']
q = q.son[target[j]-'a']
if p == nil || q == nil {
break
}
if p.sid >= 0 && q.sid >= 0 {
// 修改从 i 到 j 的这一段
res = min(res, dis[p.sid][q.sid]+dfs(j+1))
}
}
*ptr = res
return res
}
ans := dfs(0)
if ans == inf {
return -1
}
return int64(ans)
}
// 递推
func minimumCost2(source, target string, original, changed []string, cost []int) int64 {
const inf = math.MaxInt / 2
type node struct {
son [26]*node
sid int // 字符串的编号
}
root := &node{}
sid := 0
put := func(s string) int {
o := root
for _, b := range s {
b -= 'a'
if o.son[b] == nil {
o.son[b] = &node{sid: -1}
}
o = o.son[b]
}
if o.sid < 0 {
o.sid = sid
sid++
}
return o.sid
}
// 初始化距离矩阵
m := len(cost)
dis := make([][]int, m*2)
for i := range dis {
dis[i] = make([]int, m*2)
for j := range dis[i] {
if j != i {
dis[i][j] = inf
}
}
}
for i, c := range cost {
x := put(original[i])
y := put(changed[i])
dis[x][y] = min(dis[x][y], c)
}
// Floyd 求任意两点最短路
for k := 0; k < sid; k++ {
for i := 0; i < sid; i++ {
if dis[i][k] == inf {
continue
}
for j := 0; j < sid; j++ {
dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j])
}
}
}
n := len(source)
f := make([]int, n+1)
for i := n - 1; i >= 0; i-- {
if source[i] == target[i] {
f[i] = f[i+1] // 不修改 source[i]
} else {
f[i] = inf
}
p, q := root, root
for j := i; j < n; j++ {
p = p.son[source[j]-'a']
q = q.son[target[j]-'a']
if p == nil || q == nil {
break
}
if p.sid >= 0 && q.sid >= 0 {
// 修改从 i 到 j 的这一段
f[i] = min(f[i], dis[p.sid][q.sid]+f[j+1])
}
}
}
if f[0] == inf {
return -1
}
return int64(f[0])
}