→ sustainer123: 別卷了 07/27 19:30
→ oin1104: 我好崇拜你 送我模型 07/27 19:30
→ JIWP: 我是垃圾喔.jpg 07/27 19:33
2976. 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)
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.129.148 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722079780.A.39B.html