给定两个字符串 str1 和 str2 ,请你算出将 str1 转为 str2 的最少操作数。
你可以对字符串进行3种操作:
1.插入一个字符
2.删除一个字符
3.修改一个字符。
字符串长度满足 ,保证字符串中只出现小写英文字母。
"nowcoder","new"
6
"nowcoder"=>"newcoder"(将'o'替换为'e'),修改操作1次 "nowcoder"=>"new"(删除"coder"),删除操作5次
"intention","execution"
5
一种方案为: 因为2个长度都是9,后面的4个后缀的长度都为"tion",于是从"inten"到"execu"逐个修改即可
"now","nowcoder"
5
public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param str1 string字符串 * @param str2 string字符串 * @return int整型 */ public int editDistance (String str1, String str2) { int s1Len = str1.length(); int s2Len = str2.length(); // 如果有一个字符串长度等于0,那么最小变换次数即为 s1Len + s2Len; if(s1Len == 0 || s2Len == 0) return s1Len + s2Len; // 初始化dp数组,dp[i][j] 记录 str1 每一个字符 变成 str2的次数 int[][] dp = new int[s1Len + 1][s2Len + 1]; // 第一行第一列,辅助单元格 // 初始化第一行 // 可以理解为: 将一个空串,转变为str2字符串从0 ~ i的字符 所需要的次数 for (int i = 1; i < dp[0].length; i++) dp[0][i] = i; // 初始化第一列 // 可以理解为: 将str1字符串从0 ~ i的字符 转变为 一个空串 所需要的次数 for (int i = 1; i < dp.length; i++) dp[i][0] = i; // 下标从1开始遍历每一行 for (int i = 1; i < dp.length; i++) { // 取出str1的 i索引字符 char strChar1 = str1.charAt(i - 1); // 下标从1开始遍历每一列 for (int j = 1; j < dp[0].length; j++) { // 取出str2的 j索引字符 char strChar2 = str2.charAt(j - 1); // 如果相等,那么只需要取出左斜方单元格记录的次数即可 if(strChar1 == strChar2){ dp[i][j] = dp[i - 1][j - 1]; }else{ // 如果不相等,取出左斜方,上方,左方的值,取最小后 + 1 即为当前 0 ~ i索引的str1字符串变换成 0 ~ j索引的str2字符串所需要的次数 int i1 = dp[i - 1][j - 1]; int i2 = dp[i][j - 1]; int i3 = dp[i-1][j]; dp[i][j] = Math.min(i3, Math.min(i1, i2)) + 1; } } } // 循环结束,dp表格最后一个单元格记录的值,即为解 return dp[s1Len][s2Len]; } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param str1 string字符串 * @param str2 string字符串 * @return int整型 */ public int editDistance (String str1, String str2) { // write code here int[][] dp = new int[str1.length() + 1][str2.length() + 1]; //初始化 for (int i = 0; i < str1.length() + 1; i++) { for (int j = 0; j < str2.length() + 1; j++) { if (i == 0)dp[i][j] = j; if (j == 0)dp[i][j] = i; } } //开始递推 for (int i = 1; i < str1.length() + 1; i++) { for (int j = 1; j < str2.length() + 1; j++) { if (str1.charAt(i - 1) == str2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1]; else dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1; } } return dp[str1.length()][str2.length()]; } }
import java.util.*; public class Solution { private int arr[][]; /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param str1 string字符串 * @param str2 string字符串 * @return int整型 */ public int editDistance (String str1, String str2) { // write code here String longOne = str1, shortOne = str2; arr = new int[longOne.length()][shortOne.length()]; for (int i =0;i<longOne.length();i++) { for (int j =0;j<shortOne.length();j++) { arr[i][j] = 0; } } return searchDistance(longOne, shortOne, 0, 0); } public int searchDistance(String longOne, String shortOne, int longIndex, int shortIndex) { if (longOne.length() <= longIndex) { return shortOne.length() - shortIndex > 0 ? shortOne.length() - shortIndex:0; } else if (shortOne.length() <= shortIndex) { return longOne.length() - longIndex > 0 ? longOne.length() - longIndex: 0; } if(arr[longIndex][shortIndex] != 0) { return arr[longIndex][shortIndex]; } if (shortOne.charAt(shortIndex) == longOne.charAt(longIndex)) { arr[longIndex][shortIndex] = searchDistance(longOne, shortOne, longIndex + 1, shortIndex + 1); return arr[longIndex][shortIndex]; } else { int d1 = searchDistance(longOne, shortOne, longIndex + 1, shortIndex + 1); int d2 = searchDistance(longOne, shortOne, longIndex, shortIndex + 1); int d3 = searchDistance(longOne, shortOne, longIndex + 1, shortIndex ); arr[longIndex][shortIndex] = 1 + Math.min(d1, Math.min(d2,d3)); return arr[longIndex][shortIndex]; } } }
import java.util.*; public class Solution { int[][] memo; //备忘录,记录递归中间结果 public int editDistance (String word1, String word2) { int len1 = word1.length(); int len2 = word2.length(); memo = new int[len1][len2]; //初始化备忘录 for (int[] row : memo) { Arrays.fill(row, -1); } //用二个指针从二个字符串末尾开始向前遍历 return dp(word1, word2, len1- 1, len2 - 1); } //dp(i,j)表示以i的字符串s1变为以j结尾的s2的最少操作数 int dp(String s1, String s2, int i, int j) { //如果s1遍历结束,则s1添加s2的剩余字符 if (i == -1) return j + 1; //如果s2遍历结束,则s1删掉s2的剩余字符 if (j == -1) return i + 1; //如果计算过则直接返回 if (memo[i][j] != -1) { return memo[i][j]; } //如果当前位置相等,则什么都不做 if (s1.charAt(i) == s2.charAt(j)) { memo[i][j] = dp(s1, s2, i - 1, j - 1); } else { //如果不等,则进行增、删、换 //增加:i比不变,j前移。删除:i前移,j不变 int temp = Math.min(dp(s1, s2, i, j - 1), dp(s1, s2, i - 1, j)) + 1; //替换;i和j都前移 memo[i][j] = Math.min(temp, dp(s1, s2, i - 1, j - 1) + 1); } return memo[i][j]; } }
public int editDistance(String str1, String str2) { char[] s1 = str1.toCharArray(); char[] s2 = str2.toCharArray(); int len1 = s1.length; int len2 = s2.length; // 定义dp[i][j]为字符串1和2分别到i,j位置时的编辑距离 int[][] dp = new int[len1 + 1][len2 + 1]; // base case 如果其中一个为空,操作数为另一个的长度 for (int i = 0; i <= len1; i++) { dp[i][0] = i; } for (int j = 0; j <= len2; j++) { dp[0][j] = j; } /* * 动态转移方程: * 如果char[i-1] = char[j-1] 字符相等 那么 dp[i][j] = dp[i-1][j-1]; * 否则就是 增加 删除 替换 中较小的那个 dp[i][j-1] dp[i-1][j] dp[i-1][j-1] + 1; * */ for (int i = 1; i <= len1; i++) { for (int j = 1; j <= len2; j++) { if (s1[i - 1] == s2[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1; } } } return dp[len1][len2]; } public int min(int a, int b, int c) { return Math.min(a, Math.min(b, c)); }
java版——动态规划
dp[i][j] 表示 str1 的前 i 个字符和 str2 的前 j 个字符的编辑距离。
(以下说的相等是指我们已经知道它们的编辑距离)
- 如果 str1 的前 i - 1 个字符和 str2 的前 j 个字符相等,那么我们只需要在 str1 最后插入一个字符就可以转化为 str2 。 dp[i][j] = dp[i - 1][j] + 1
- 如果 str1 的前 i 个字符和 str2 的前 j - 1 个字符相等,那么我们只需要在 str1 最后删除一个字符就可以转化为 str2 。 dp[i][j] = dp[i][j - 1] + 1
- 如果 str1 的前 i - 1 个字符和 str2 的前 j - 1 个字符相等,那么我们要判断 str1 和 str2 最后一个字符是否相等:
- 如果相等,则不需要任何操作。 dp[i][j] = dp[i - 1][j - 1]
- 如果不相等,则只需要将 str1 最后一个字符修改为 str2 最后一个字符即可。dp[i][j] = dp[i - 1][j - 1] + 1
最终 dp[i][j] 为上面三种状态的最小值:
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
奥,对了,我们还要考虑边界情况,当str1为空时,编辑距离就为str2的长度(str1依次插入str2个字符),当str2为空时编辑距离就为str1的长度(str1依次删除每个字符)。
import java.util.*; public class Solution { public int editDistance (String str1, String str2) { // write code here int len1 = str1.length(); int len2 = str2.length(); if(len1 == 0 || len2 == 0){ return len1 + len2; } int[][] dp = new int[len1 + 1][len2 + 1]; for(int i = 0; i <= len1; i++){ dp[i][0] = i; } for(int j = 0; j <= len2; j++){ dp[0][j] = j; } for(int i = 1; i <= len1; i++){ for(int j = 1; j <= len2; j++){ if(str1.charAt(i - 1) == str2.charAt(j - 1)){ dp[i][j] = dp[i - 1][j - 1]; }else{ dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1; } } } return dp[len1][len2]; } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * @param str1 string字符串 * @param str2 string字符串 * @return int整型 */ public int editDistance (String str1, String str2) { // write code here //str1前i个字符转换到str2前j个字符的最少操作数 int[][] dp = new int[str1.length()+1][str2.length()+1]; //如果后字符串全为空,则全删除 for(int i=0; i<=str1.length(); i++){ dp[i][0] = i; } //如果前字符串全为空,则全添加 for(int j=0; j<=str2.length(); j++){ dp[0][j] = j; } for(int i=1; i<=str1.length(); i++){ for(int j=1; j<=str2.length(); j++){ if(str1.charAt(i-1)==str2.charAt(j-1)){ dp[i][j] = dp[i-1][j-1]; }else{ dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1; } } } return dp[str1.length()][str2.length()]; } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param str1 string字符串 * @param str2 string字符串 * @return int整型 */ public int editDistance (String str1, String str2) { // write code here int[][] dp = new int[str1.length() + 1][str2.length() + 1]; // 将空串编辑成str1[:i]只能不断插入字符 for(int i = 1; i <= str1.length(); i++){ dp[i][0] = dp[i - 1][0] + 1; } // 将空串编辑成str2[:j]只能不断插入字符 for(int j = 1; j <= str2.length(); j++){ dp[0][j] = dp[0][j - 1] + 1; } for(int i = 1; i <= str1.length(); i++){ for(int j = 1; j <= str2.length(); j++){ if(str1.charAt(i - 1) == str2.charAt(j - 1)){ dp[i][j] = dp[i - 1][j - 1]; }else{ dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1; } } } return dp[str1.length()][str2.length()]; } }