→ Smallsh: 大師 07/28 02:13
2024-07-28
2976. Minimum Cost to Convert String I
You are given two 0-indexed strings source and target, both of length n and
consisting of lowercase English letters. You are also given two 0-indexed
character arrays original and changed, and an integer array cost, where
cost[i] represents the cost of changing the character original[i] to the
character changed[i].
You start with the string source. In one operation, you can pick a character
x from the string and change it to the character y at a cost of z if there
exists any index j such that cost[j] == z, original[j] == x, and changed[j]
== y.
Return the minimum cost to convert the string source to the string target
using any number of operations. If it is impossible to convert source to
target, return -1.
Note that there may exist indices i, j such that original[j] == original[i]
and changed[j] == changed[i].
這個應該就dynamic programming
先串出所有字元的轉換 cost
然後 source -> target 就照 cost 加起來
沒空寫繼續抄解答的第N天
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 73.173.211.221 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722103829.A.589.html
※ 編輯: smart0eddie (73.173.211.221 美國), 07/28/2024 02:10:54