链接
LeetCode_72_编辑距离
题目
给你两个单词 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')
思路
一、状态定义
dp数组模型:
假设字符串1( "mice" ) 为 s1, 它的长度为 n1; 字符串2( "arise" ) 为 s2, 它的长度为 n2
dp是大小为(n1 + 1) * (n2 +1) 的二维数组 dp[ i ] [ j ]是 s1[0, i) 转换成 s2[0, j) 的最少操作数 s1[0, i) 是由 s1 的前 i 个字符组成的子串 s2[0, j) 是由 s2 的前 j 个字符组成的子串
很显然, dp[ n1 ][ n2 ]就是最终答案, 就是s1[0, n1)转换成s2[0, n2)的最少操作数 就是s1转换成s2的最少操作数
二、初始化状态
最左上角的dp[0][0]: 代表s1的空子串转换为s2的空子串的最少操作数 其实就是什么也不需要做, 所以: dp[0][0] = 0
第0列的dp[i][0]: 代表s1[0,i)转换为s2的空子串的最少操作数 其实就是删除s1[0,i)的所有字符, 所以: dp[i][0] = i
第0行的dp[0][j]: 代表s1的空子串转换为s2[0,j)的最少操作数 其实就是插入s2[0,j)的所有字符, 所以: dp[0][j] = j
三、状态转移方程
dp[i][j]是s1[0, j)转换成s2[0, j)的最少操作数 可以分四种情况讨论:
① 先删除s1[0, i)的最后一个字符得到s1[0, i-1) 然后由s1[0, i-1)转换为s2[0, j) 这种情况下, dp[ i ][ j ] = 1 + dp[ i-1 ][ j ]
② 先由s1[0, i)转换为s2[0, j-1), 然后在最后插入字符s2[ j-1 ], 得到s2[0, j) 这种情况下, dp[ i ][ j ] = dp[ i ][ j-1 ] + 1
③ 如果s1[ i-1 ] != s2[ j-1 ], 先由s1[0, i-1)转换为s2[0, j-1) 然后将s1[ i-1 ]替换为s2[ j-1 ], 这种情况下, dp[ i ][ j ] = dp[ i-1 ][ j-1 ] + 1
④ 如果s1[ i-1 ] == s2[ j-1 ], 由s1[0, i-1)转换为s2[0, j-1)后就不用再做任何操作 这种情况下, dp[ i ][ j ] = dp[ i-1 ][ j-1 ]
题解
/**
* 思路: 动态规划
* dp(i,j): word1前i个字符转为字word2前j个字符所用的最少操作次数
* dp(0,j) = j, dp(i,0) = i
* dp(i,j) = min{
* dp(i-1,j)+1, ==> word1前i-1个字符转为word2前j个字符所用最少操作次数 + 1
* dp(i,j-1)+1, ==> word1前i个字符转为word2前j-1个字符所用的最少操作次数 + 1
* if(word1[i]==word[j]) dp(i-1,j-1) else dp(i-1,j-1)+1
* ==> 如果word1第i-1个字符和word2第j-1个字符相同,即第i-1个字符不需要转换, 那么word1前i个字符转为word2前j个字符所用的最少操作次数与word1前i-1个字符转为word2前j-1个字符所用的最少操作次数相同;
* 否则, word1前i-1个字符转为word2前j-1个字符所用的最少操作次数 + 1
* }
*/
public int minDistance_(String word1, String word2) {
if(word1 == null || word2 == null) return 0;
char[] chars1 = word1.toCharArray();
char[] chars2 = word2.toCharArray();
if(chars2.length == 0) return chars1.length;
if(chars1.length == 0) return chars2.length;
int[][] dp = new int[chars1.length+1][chars2.length+1];
//dp数组初始化
dp[0][0] = 0;
for (int i = 1; i <= chars1.length; i++) {
dp[i][0] = i;
}
for (int i = 1; i <= chars2.length; i++) {
dp[0][i] = i;
}
//状态转移计算
for (int i = 1; i <= chars1.length; i++) {
for (int j = 1; j <= chars2.length; j++) {
int tmp = dp[i-1][j-1]; //假设word1第i-1个字符和word2第j-1个字符相同
if(chars1[i-1] != chars2[j-1]){
tmp = tmp + 1;
}
dp[i][j] = Math.min(tmp,Math.min(dp[i-1][j] + 1,dp[i][j-1] + 1));
}
}
return dp[chars1.length][chars2.length];
}
空间复杂度优化(dp二维数组转一维数组)
/**
* 思路: 动态规划 (空间复杂度优化)
* dp(i,j): word1前i个字符转为字word2前j个字符所用的最少操作次数
* dp(0,j) = j, dp(i,0) = i
* dp(i,j) = min{
* dp(i-1,j)+1, ==> word1前i-1个字符转为word2前j个字符所用最少操作数 + 1
* dp(i,j-1)+1, ==> word1前i个字符转为word2前j-1个字符所用的最少操数 + 1
* if(word1[i]==word[j]) dp(i-1,j-1) else dp(i-1,j-1)+1
* ==> 如果word1第i-1个字符和word2第j-1个字符相同,即第i-1个字符不需要转换, 那么word1前i个字符转为word2前j个字符所用的最少操数与word1前i-1个字符转为word2前j-1个字符所用的最少操数相同;
* 否则, word1前i-1个字符转为word2前j-1个字符所用的最少操数 + 1
* }
*/
public int minDistance(String word1, String word2) {
if(word1 == null || word2 == null) return 0;
char[] chars1 = word1.toCharArray();
char[] chars2 = word2.toCharArray();
if(chars2.length == 0) return chars1.length;
if(chars1.length == 0) return chars2.length;
int[] dp = new int[chars2.length+1];
//dp数组初始化, 如果words1为空,则转换为word2前i个字符所需要的操作次数
for (int i = 0; i <= chars2.length; i++) {
dp[i] = i;
}
//状态转移计算
for (int i = 1; i <= chars1.length; i++) {
int leftTop = dp[0]; //上一行dp[0]的值
dp[0] = i; //更新本行dp[0]的值
for (int j = 1; j <= chars2.length; j++) {
int tmp = leftTop;
leftTop = dp[j]; //保存旧的dp[j],下一轮循环中使用
if(chars1[i-1] != chars2[j-1]){
tmp = tmp + 1;
}
dp[j] = Math.min(tmp,Math.min(dp[j] + 1,dp[j-1] + 1));
}
}
return dp[chars2.length];
}
