LeetCode(72):编辑距离
Hard!
题目描述:
给定两个单词 word1 和 word2,计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1:
输入: word1 = "horse", word2 = "ros" 输出: 3 解释: horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')
示例 2:
输入: word1 = "intention", word2 = "execution" 输出: 5 解释: intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u')
解题思路:
这道题让求从一个字符串转变到另一个字符串需要的变换步骤,共有三种变换方式,插入一个字符,删除一个字符,和替换一个字符。根据以往的经验,对于字符串相关的题目十有八九都是用动态规划Dynamic Programming来解,这道题也不例外。
这道题我们需要维护一个二维的数组dp,其中dp[i][j]表示从word1的前i个字符转换到word2的前j个字符所需要的步骤。那我们可以先给这个二维数组dp的第一行第一列赋值,这个很简单,因为第一行和第一列对应的总有一个字符串是空串,于是转换步骤完全是另一个字符串的长度。跟以往的DP题目类似,难点还是在于找出递推式,我们可以举个例子来看,比如word1是“bbc",word2是”abcd“,那么我们可以得到dp数组如下:
Ø a b c d Ø 0 1 2 3 4 b 1 1 1 2 3 b 2 2 1 2 3 c 3 3 2 1 2
通过观察可以发现,当word1[i] == word2[j]时,dp[i][j] = dp[i - 1][j - 1],其他情况时,dp[i][j]是其左,左上,上的三个值中的最小值加1,那么可以得到递推式为:
dp[i][j] = / dp[i - 1][j - 1] if word1[i - 1] == word2[j - 1]
\ min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1 else
C++解法一:
1 class Solution { 2 public: 3 int minDistance(string word1, string word2) { 4 int n1 = word1.size(), n2 = word2.size(); 5 int dp[n1 + 1][n2 + 1]; 6 for (int i = 0; i <= n1; ++i) dp[i][0] = i; 7 for (int i = 0; i <= n2; ++i) dp[0][i] = i; 8 for (int i = 1; i <= n1; ++i) { 9 for (int j = 1; j <= n2; ++j) { 10 if (word1[i - 1] == word2[j - 1]) { 11 dp[i][j] = dp[i - 1][j - 1]; 12 } else { 13 dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1; 14 } 15 } 16 } 17 return dp[n1][n2]; 18 } 19 };
相关文章
- Java实现 LeetCode 819 最常见的单词(暴力)
- Java实现 LeetCode 648 单词替换(字典树)
- Java实现 LeetCode 149 直线上最多的点数
- Java实现 LeetCode 139 单词拆分
- Java实现 LeetCode 42 接雨水
- 【二叉树】LeetCode 102. 二叉树的层序遍历【中等】
- LeetCode(72):编辑距离
- LeetCode(22):括号生成
- 72. 编辑距离——【Leetcode每日一题】
- Python 刷Leetcode题库,顺带学英语单词(50)
- Leetcode 剑指 Offer II 032. 有效的变位词
- 【leetcode】sort list(python)
- LeetCode总结 -- 高精度篇
- leetcode 559. Maximum Depth of N-ary Tree