[LeetCode] 72. 编辑距离 ☆☆☆☆☆(动态规划)
https://leetcode-cn.com/problems/edit-distance/solution/bian-ji-ju-chi-mian-shi-ti-xiang-jie-by-labuladong/ (思路很好,有图很好理解)
描述
给定两个单词 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')
解析
编辑距离可以用来比较二者的相似度。编辑距离越小,说明越相似。
编辑距离问题就是给我们两个字符串 s1 和 s2,只能用三种操作,让我们把 s1 变成 s2,求最少的操作数。需要明确的是,不管是把 s1 变成 s2 还是反过来,结果都是一样的。
解决两个字符串的动态规划问题,一般都是用两个指针 i,j
分别指向两个字符串的最后,然后一步步往前走,缩小问题的规模。
定义数组的含义
由于我们的目的求将 word1 转换成 word2 所使用的最少操作数 。那我们就定义 dp[i] [j]的含义为:当字符串 word1 的长度为 i,字符串 word2 的长度为 j 时,将 word1 转化为 word2 所使用的最少操作次数为 dp[i] [j]。
找出关系数组元素间的关系式
接下来我们就要找 dp[i] [j] 元素之间的关系了,比起其他题,这道题相对比较难找一点,但是,不管多难找,大部分情况下,dp[i] [j] 和 dp[i-1] [j]、dp[i] [j-1]、dp[i-1] [j-1] 肯定存在某种关系。因为我们的目标就是,从规模小的,通过一些操作,推导出规模大的。对于这道题,我们可以对 word1 进行三种操作
插入一个字符
删除一个字符
替换一个字符
由于我们是要让操作的次数最小,所以我们要寻找最佳操作。那么有如下关系式:
一、如果我们 word1[i] 与 word2 [j] 相等,这个时候不需要进行任何操作,显然有 dp[i] [j] = dp[i-1] [j-1]。(别忘了 dp[i] [j] 的含义哈)。
二、如果我们 word1[i] 与 word2 [j] 不相等,这个时候我们就必须进行调整,而调整的操作有 3 种,我们要选择一种。三种操作对应的关系试如下(注意字符串与字符的区别):
(1)、如果把字符 word1[i] 替换成与 word2[j] 相等,则有 dp[i] [j] = dp[i-1] [j-1] + 1;
(2)、如果在字符串 word1末尾插入一个与 word2[j] 相等的字符,则有 dp[i] [j] = dp[i] [j-1] + 1;
(3)、如果把字符 word1[i] 删除,则有 dp[i] [j] = dp[i-1] [j] + 1;
(可以用第一个链接来帮助理解)
那么我们应该选择一种操作,使得 dp[i] [j] 的值最小,显然有
dp[i] [j] = min(dp[i-1] [j-1],dp[i] [j-1],dp[[i-1] [j]]) + 1;
于是,我们的关系式就推出来了。
初始值
当 dp[i] [j] 中,如果 i 或者 j 有一个为 0,那么还能使用关系式吗?答是不能的,因为这个时候把 i - 1 或者 j - 1,就变成负数了,数组就会出问题了,所以我们的初始值是计算出所有的 dp[0] [0….n] 和所有的 dp[0….m] [0]。这个还是非常容易计算的,因为当有一个字符串的长度为 0 时,转化为另外一个字符串,那就只能一直进行插入或者删除操作了。
代码
public int minDistance(String word1, String word2) {
if (word1 == null || word1.length() <= 0) {
return word2.length();
} else if (word2 == null || word2.length() <= 0) {
return word1.length();
}
int length1 = word1.length();
int length2 = word2.length();
int[][] array = new int[length1 + 1][length2 + 1];// +1,是因为数组的length2位置有实际意义,表示length2位置的编辑距离
for (int i = 0; i <= length1; i++) {
array[i][0] = i;
}
for (int i = 0; i <= length2; i++) {
array[0][i] = i;
}
for (int ii = 1; ii <= length1; ii++) {
for (int kk = 1; kk <= length2; kk++) {
if (word1.charAt(ii - 1) == word2.charAt(kk - 1)) {
array[ii][kk] = array[ii - 1][kk - 1];
} else {
array[ii][kk] = Math.min(array[ii - 1][kk - 1], Math.min(array[ii][kk - 1], array[ii - 1][kk])) + 1;
}
}
}
return array[length1][length2];
}
优化:可以和[LeetCode] 62. 不同路径 ☆☆☆(动态规划)的思路一下去优化,因为每次计算只用到2行数据。
public int minDistance(String word1, String word2) {
int n1 = word1.length();
int n2 = word2.length();
int[] dp = new int[n2 + 1];
// dp[0...n2]的初始值
for (int j = 0; j <= n2; j++)
dp[j] = j;
// dp[j] = min(dp[j-1], pre, dp[j]) + 1
for (int i = 1; i <= n1; i++) {
int temp = dp[0]; // 相当于初始化
dp[0] = i;// 第 i 行第 0 列的初始值
for (int j = 1; j <= n2; j++) {
// pre 相当于之前的 dp[i-1][j-1]
int pre = temp;
temp = dp[j];// 在下一次temp被赋值给pre时,相当于dp[i-1][j-1]
// 如果 word1[i] 与 word2[j] 相等。第 i 个字符对应下标是 i-1
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[j] = pre;
} else {
dp[j] = Math.min(Math.min(dp[j - 1], pre), dp[j]) + 1;
}
}
}
return dp[n2];
}
最新文章
- dedecms调用子栏目内容,缩略图,以及栏目名字
- jsoncpp 生成 json 字符串
- XMPP协议、IM、客户端互联详解
- 主机win10与虚拟机ubuntu14.04通信
- 【转】构建maven web项目
- spring的三种注解管理器
- 服务器部署_linux下部署jprofiler简单备忘
- evernote出现“Sync failed due to unexpected problem at server side”的问题
- WinFrom中使用WPF的窗体
- Vmware Tools 下载及安装方法
- dotweb框架之旅 [四] - 常用对象-HttpContext
- JAVA 锁之 Synchronied
- java:多层文件夹情况下,判断文件夹下是否有文件夹,并获取到没有文件夹的名字的方法
- GROUP BY你都不会!ROLLUP,CUBE,GROUPPING详解
- mysql8.0 定时创建分区表记录 每天定时创建下一天的分区表
- 51nod 1405 树的距离之和 树形dp
- Far manager界面混乱问题解决
- ethereum/EIPs-161 State trie clearing
- 常用的 git 命令
- JAVA中 XML与数据库互转 学习笔记三