描述
给定两个字符串 str1 和 str2 ，请你算出将 str1 转为 str2 的最少操作数。
你可以对字符串进行3种操作：
1.插入一个字符
2.删除一个字符
3.修改一个字符。
image.png
思路：
1、初始条件： 假设第二个字符串为空，那很明显第一个字符串子串每增加一个字符，编辑距离就加1，这步操作是删除；同理，假设第一个字符串为空，那第二个字符串每增加一个字符，编剧距离就加1，这步操作是添加。 dp[i][0] 和 dp[0][j] 初始化从1开始
2、如果str1 i位置对应 str2 j位置相等字符，那么操作次数与两个子串的前一个相同dp[i][j] = dp[i-1][j-1]；
如果不相等， dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
public int editDistance (String str1, String str2) {
// write code here
int length1 = str1.length();
int length2 = str2.length();
int[][] dp = new int[length1+1][length2+1];
for(int i = 1;i<=length1;i++){
dp[i][0] = dp[i-1][0]+1;
}
for(int i = 1;i<=length2;i++){
dp[0][i] = dp[0][i-1]+1;
}
for(int i = 1;i<=length1;i++){
for(int j = 1;j<=length2;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[length1][length2];
}
