可以做自己的单机网站,大型电商平台有哪些,网页制作框架模板的步骤,做网站的销售怎么样题目#xff1a;HJ52 计算字符串的编辑距离 题解#xff1a;
定义dp方程#xff0c;dp[i][j] 表示字符串s1(1-i)#xff0c;到字符串s2(1-j)的编辑距离#xff1b;
如果s1[i] s2[j] 证明当前位置的字符相等#xff0c;无需操作#xff0c;即dp[i][j] dp[i-1][j-1]; …题目HJ52 计算字符串的编辑距离 题解
定义dp方程dp[i][j] 表示字符串s1(1-i)到字符串s2(1-j)的编辑距离
如果s1[i] s2[j] 证明当前位置的字符相等无需操作即dp[i][j] dp[i-1][j-1];
如果s1[i] ! s2[j] 则需要进行修改有三种修改方式
1.删除s1(1 - i-2) 编辑为 s2(1 - j-1) 在删除s1[i-1];
2.插入s1(1 - i-1) 编辑为 s2(1 - i-2) 再插入s2[j-1];
3.修改s1(1 - i-2) 编辑为 s2(1 - i-) 再将s1[i-1] 修改为 s2[i-1)
三种修改操作都需要增加一次编辑次数然后取最小的一个。 dp 初始化 dp[i][0] 表示s1(1-i)编辑为空那么需要删除s1的所有字符即dp[i][0]i;
同理dp[0][i]i; public int getDistance(String s1, String s2) {int n s1.length();int m s2.length();int[][] dp new int[n 1][m 1];for (int i 1; i n 1; i) {dp[i][0] i;}for (int i 1; i m 1; i) {dp[0][i] i;}for (int i 1; i n 1; i) {for (int j 1; j m 1; j) {if (s1.charAt(i - 1) s2.charAt(j - 1)) {dp[i][j] dp[i - 1][j - 1];} else {dp[i][j] Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) 1;}}}return dp[n][m];}
时间复杂度O(n*m)
