Problem:
Edit distance between 2 strings with dictionary based cost

这场是 TikTok 一轮算法面试
给两个字符串 word1、word2，以及一份 cost dictionary。将 word1 转换成 word2，每一步操作的代价由字典提供，求最小总成本。

面试官给出的题目是在经典编辑距离基础上加入 cost dictionary，每一步操作的代价需要通过映射查询得到，目标是计算从 word1 转换到 word2 的最小总代价。

候选人进入题目后先对规则进行确认，包括操作类型是否覆盖 insert、delete、replace，以及字典中不存在的操作如何处理。随后直接将问题抽象为标准二维动态规划模型。

状态定义沿用 edit distance 的结构，dp[i][j] 表示 word1 前 i 个字符转换为 word2 前 j 个字符的最小成本。初始化阶段需要逐字符累加 cost，空串到目标串通过插入得到，原串到空串通过删除得到，所有代价均来自 dictionary。

转移过程围绕三个方向展开：从左侧状态延伸表示插入，从上方状态延伸表示删除，从左上角状态延伸表示字符匹配或替换。字符相同时直接继承原状态，不同时通过 dictionary 查询替换代价并累加。整个过程保持标准 DP 结构，所有权重来自外部映射。

实现阶段在 Java 环境中完成二维 DP 表构建，复杂度为 O(mn)。空间可以进一步压缩为一维滚动数组，这一点在讲解阶段也进行了说明。

在 csoahelp 的辅助过程中，候选人在建模阶段快速确认了状态定义的表达方式，同时将 dictionary cost 自然嵌入到初始化和转移中。编码阶段基于 edit distance 模板快速展开，将固定 cost 替换为查询逻辑，并对空字符串和缺失 cost 的情况做了补充处理。最后在解释环节整理出完整的状态转移路径和复杂度表达，整体过程流畅稳定。

整道题围绕 edit distance 的基础模型展开，所有变化集中在 cost 来源，核心结构保持一致，重点体现在状态转移中对映射代价的处理。

需要这种面试级别的实时思路梳理和代码辅助，可以直接使用 csoahelp 全程陪你拿下算法面试。

我们也有代面试，面试辅助，OA代写等服务助您早日上岸~