编辑距离问题

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作： 插入一个字符 删除一个字符 替换一个字符 输入：word1 = "horse", word2 = "ros" 输出：3 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e') 输入：word1 = "intention", word2 = "execution" 输出：5 解释： intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u')

分析问题:

一共有四钟操作: 插入,删除,替换,跳过

if s1[i] == s2[j]: 啥都别做（skip） i, j 同时向前移动 else: 三选一： 插入（insert） 删除（delete） 替换（replace）

所以可以用递归

(1) 确定函数 int dp(int i,int j,string& word1,string& word2)//这个函数的作用就是,返回s1[0,i] s2[0,j]的最小编辑距离

(2) 终止条件

if(i==-1) return j+1;//也就是 i没有,那么我的j就要操作size()下删除 if(j==-1) return i+1;

(3)函数作用实现及返回上一层什么: 返回三种操作中的最小值

所以最后实现

class Solution { public: //解法一,递归 int minDistance(string word1, string word2) { //递归解决,方法如下 int res=dp(word1.size()-1,word2.size()-1,word1,word2); return res; } int dp(int i,int j,string& word1,string& word2)//这个函数的作用就是,返回s1[0,i] s2[0,j]的最小编辑距离 { //边界条件 if(i==-1) return j+1;//也就是 i没有,那么我的j就要操作size()下插入 if(j==-1) return i+1; //在四总操作取最小的编辑距离,返回上一层我们这一层计算得到的结果 if(word1[i]==word2[j]) return dp(i-1,j-1,word1,word2); else if(word1[i]!=word2[j]) { //返回删除,插入,替换的最小操作距离 int tmp=min(dp(i-1,j,word1,word2)+1,dp(i,j-1,word1,word2)+1);//比较删除和插入操作 return min(tmp,dp(i-1,j-1,word1,word2)+1); } return -1; } };

因为,递归存在重复的子问题,所以可以用动态规划进行优化(备忘录或dp table)

可以参考这篇博客)

class Solution { public: //解法二,动态规划 int minDistance(string word1, string word2) { int row=word1.size()+1; int col=word2.size()+1;//s1->s2 // if(row==0&&col==0) return 0; // if(row==0) return col; // if(col==0) return row; vector<vector<int>> dp(row,vector<int>(col,0)); //初始化dp table for(int i=0;i<col;i++) { dp[0][i]=i; } for(int j=0;j<row;j++) { dp[j][0]=j; } //写出状态转移方程 for(int i=1;i<row;i++) { for(int j=1;j<col;j++) { if(word1[i-1]==word2[j-1]) { dp[i][j]=dp[i-1][j-1]; continue; } else if(word1[i-1]!=word2[j-1]) { int tmp=min(dp[i-1][j]+1,dp[i][j-1]+1); dp[i][j]=min(tmp,dp[i-1][j-1]+1); } } } return dp[row-1][col-1]; } };