楼主:
JIWP (JIWP)
2024-07-27 19:29:372976. Minimum Cost to Convert String I
给两个长度n的string : source、target
两个长度一样的字符矩阵original、changed
以及长度和字符矩阵一样长的整数矩阵cost
cost[i]表示从original[i]换到changed[i]所需要的成本
请问从source换到target所需要最少的成本
如果没办法换过去请回传-1
思路:
求出每个字母到其他字母的最短路径
就用Floyd-Warshall算法
然后要记得会有original[i]==original[j]、target[i]==target[j]的情况存在
在求最短路径的时候要做对应的处理
golang code :
func minimumCost(source string, target string, original []byte, changed []byte
, cost []int) int64 {
paths := make([][]int, 26)
res := 0
for i := 0; i < 26; i++ {
paths[i] = make([]int, 26)
for j := 0; j < 26; j++ {
paths[i][j] = math.MaxInt32
}
paths[i][i] = 0
}
for i := 0; i < len(original); i++ {
idxi, idxj := int(original[i]-'a'), int(changed[i]-'a')
if paths[idxi][idxj] > cost[i] {
paths[idxi][idxj] = cost[i]
}
}
for k := 0; k < 26; k++ {
for i := 0; i < 26; i++ {
for j := 0; j < 26; j++ {
if paths[i][j] > paths[i][k]+paths[k][j] {
paths[i][j] = paths[i][k] + paths[k][j]
}
}
}
}
for i := 0; i < len(source); i++ {
idxi, idxj := int(source[i]-'a'), int(target[i]-'a')
if paths[idxi][idxj] == math.MaxInt32 {
return -1
}
res += paths[idxi][idxj]
}
return int64(res)
}