leetcode72：编辑距离
-
题目：给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符 删除一个字符 替换一个字符
-
思路：
-
使用双指针遍历两个单词；
-
当两个单词指针指向的字符相同，则两个单词均指向下一个字符；
-
当两个单词指针指向的字符不同，取进行删除、插入、替换任一种操作后的最优解。
-
解法1：
class Solution {
? ?//定义备忘录，解决重叠子问题
? ?int[][] meno;
? ?public int minDistance(String word1, String word2) {
? ? ? ?int n = word1.length();
? ? ? ?int m = word2.length();
? ? ? ?meno = new int[n][m];
? ? ? ?for(int[] row : meno){
? ? ? ? ? ?Arrays.fill(row,-1);
? ? ? }
?
? ? ? ?return dp(word1,n-1,word2,m-1);
?
? ? ? ?
?
? }
? ?public int dp(String word1,int i,String word2,int j){
? ? ? ?
? ? ? ?//base case
? ? ? ?//遇到任何一个单词走完了，则返回未走完的单词的数组下标加1
? ? ? ?//对另一个单词进行插入或者删除 未走完单词的长度即（j+1或i+1） 个操作
? ? ? ?if(i==-1) return j+1;
? ? ? ?if(j==-1) return i+1;
? ? ? ?if(meno[i][j]!=-1){
? ? ? ? ? ?return meno[i][j];
? ? ? }
? ? ? ?//如果两个单词指向的字符相同，则两个单词均指向下一个字符
? ? ? ?if(word1.charAt(i)==word2.charAt(j)){
? ? ? ? ? ?meno[i][j] = dp(word1,i-1,word2,j-1);
? ? ? }else{
? ? ? ? ? ?//当两个单词指向的字符不同，取进行删除、插入、替换任一种操作后的最优解
? ? ? //此种操作存在重叠子问题，故使用备忘录数组解决
? ? ? ? ? ?meno[i][j] = ?min(
? ? ? ? ? ? ? ?dp(word1,i-1,word2,j)+1,//删除操作
? ? ? ? ? ? ? ?dp(word1,i,word2,j-1)+1,//插入操作
? ? ? ? ? ? ? ?dp(word1,i-1,word2,j-1)+1//替换操作
? ? ? ? ? );
? ? ? }
?
? ? ? ?return meno[i][j];
? }
? ?public int min(int a,int b, int c){
? ? ? ?return Math.min(a,Math.min(b,c));
? }
}
解法2：
class Solution {
? ?//定义备忘录，解决重叠子问题
? ?int[][] meno;
? ?public int minDistance(String word1, String word2) {
? ? ? ?int n = word1.length();
? ? ? ?int m = word2.length();
? ? ? ?meno = new int[n+1][m+1];
? ? ? ?for(int[] row : meno){
? ? ? ? ? ?Arrays.fill(row,-1);
? ? ? }
?
? ? ? ?int[][] dp = new int[n+1][m+1];
?
? ? ?
? ? ? ?for(int i =1;i<=n;i++){
? ? ? ? ? ?dp[i][0]=i;
? ? ? }
? ? ? ?for(int i =1;i<=m;i++){
? ? ? ? ? ?dp[0][i] = i;
? ? ? }
? ? ? ?
? ? ? ?for(int i =1;i<=n;i++){
? ? ? ? ? ?for(int j =1 ;j<=m;j++){
? ? ? ? ? ? ? ?if(meno[i][j]!=-1){
? ? ? ? ? ? ? ? ? ?dp[i][j]=meno[i][j];
? ? ? ? ? ? ? ? ? ?continue;
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?if(word1.charAt(i-1)==word2.charAt(j-1)){
? ? ? ? ? ? ? ? ? ?dp[i][j]=dp[i-1][j-1];
? ? ? ? ? ? ? ? ? ?meno[i][j] = dp[i][j];
? ? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? ? ?dp[i][j]= min(
? ? ? ? ? ? ? ? ? ? ? ?dp[i-1][j]+1,
? ? ? ? ? ? ? ? ? ? ? ?dp[i][j-1]+1,
? ? ? ? ? ? ? ? ? ? ? ?dp[i-1][j-1]+1
? ? ? ? ? ? ? ? ? );
? ? ? ? ? ? ? ? ? ?meno[i][j] = dp[i][j];
?
? ? ? ? ? ? ? }
? ? ? ? ? }
? ? ? }
?
? ? ? ?return dp[n][m];
?
? ? ? ?
?
? }
?
? ?public int min(int a,int b, int c){
? ? ? ?return Math.min(a,Math.min(b,c));
? }
}
