Leetcode编程算法随笔(难度1882 Floyed算法 动态规划)2976. 转换字符串的最小成本 I

题目

https://leetcode.cn/problems/minimum-cost-to-convert-string-i/description/

给你两个下标从 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 转换为字符串 target 所需的最小成本。如果不可能完成转换，则返回 -1 。

注意，可能存在下标 i 、j 使得 original[j] == original[i] 且 changed[j] == changed[i] 。

• 1 <= source.length == target.length <= 105
• source target 均由小写英文字母组成
• 1 <= cost.length== original.length == changed.length <= 2000
• original[i] changed[i] 是小写英文字母
• 1 <= cost[i] <= 106
• original[i] != changed[i]

示例 ：

输入：

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" ：

 - 更改下标 1 处的值 'b' 为 'c' ，成本为 5 。 

- 更改下标 2 处的值 'c' 为 'e' ，成本为 1 。

 - 更改下标 2 处的值 'e' 为 'b' ，成本为 2 。 

- 更改下标 3 处的值 'd' 为 'e' ，成本为 20 。 

产生的总成本是 5 + 1 + 2 + 20 = 28 。 可以证明这是可能的最小成本。