⭐ 题目日期：

腾讯 - 2024/12/17

🌳 题目描述：

给定两个字符串 word1 和 word2，计算从字符串 word1 转换为 word2 所需的最少操作次数，允许的操作包括：

• 插入一个字符
• 删除一个字符
• 替换一个字符

示例 1：
输入：word1 = "kitten", word2 = "sitting"
输出：3

解释：即从 "kitten" 转换成 "sitting" 最少需要 3 次操作：

1. 替换 'k' 为 's'：kitten -> sitten
2. 替换 'e' 为 'i'：sitten -> sittin
3. 添加 'g'：sittin -> sitting

🕵🏽 面试评估：

这道题主要考察候选者能否用动态规划的思想将字符串编辑距离问题拆解为多个子问题，并根据三种不同的操作推导出正确的状态转移方程，从而得到最小编辑操作数。

🧗难度系数：

⭐️ ⭐️ ⭐️ ⭐️ ⭐️

提示

思路分析，题解，代码，复杂度分析仅对算法/后端训练营用户开放