编辑距离问题学习

给定两个字符串，需要判定两个字符串的编辑距离，对于两个字符串的编辑方法有三种

• 插入一个字符
• 删除一个字符
• 替换一个字符

状态转移方程：

s1的第i个字符和s2的第j个字符时，编辑距离用$f(i,j)$表示

状态转移方程为

$f(i,j)=\begin{cases}min(f(i-1,j-1)+(s1[i]==s2[j]),f(i-1,j)+1,f(i-1,j)+1),i!=0,j!=0\\j,i=0\\i,j=0\end{cases}$

这样就可以用dp解了

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n1=word1.size(),n2=word2.size();
        vector<vector<int>> dp(n1+1,vector<int>(n2+1));
        for(int i=0;i<=n1;i++){
            dp[i][0]=i;
        }
        for(int j=0;j<=n2;j++){
            dp[0][j]=j;
        }
        for(int i=1;i<=n1;i++){
            for(int j=1;j<=n2;j++){
                dp[i][j]=min(dp[i][j-1]+1,min(dp[i-1][j]+1,dp[i-1][j-1]+(word1[i-1]!=word2[j-1])));
            }
        }
        return dp[n1][n2];
    }
};