TikTok VO 面试真题解析：Edit Distance Between 2 Strings With Dictionary-Based Cost

Edit distance between 2 strings with dictionary-based cost

这道题本质上是经典编辑距离的变体：给定两个字符串，需要通过插入、删除、替换等操作把一个字符串变成另一个字符串，但每种操作的代价不是固定值，而是由字典规则决定。解题时通常用动态规划来维护前缀之间的最小转换成本，状态表示把一个字符串的前 i 个字符转换成另一个字符串的前 j 个字符的最小代价。转移时分别考虑删除、插入和替换三种操作，并结合字典中定义的字符 / 操作费用进行计算。重点是正确建模成本来源，并在二维 DP 中找到全局最优解。