题解 | #编辑距离#

// 状态：F(i,j)-->word1的前i个字符变成word2的前j个字符
// 转移方程：通过一步变成F(i,j)的状态有三种：
//          F(i-1,j)删除word1第i个字符
//          F(i,j-1)插入一个字符即word2的第j个字符
//          F(i-1,j-1)替换word1的第i个字符为word2的第j个字符(但是如果原本就相等就不会加这一步替换了)
//          so:F(i,j)=min(F(i-1,j)+1,F(i,j-1)+1,word1[i-1]==word2[j-1]?F(i-1,j-1)):F(i-1,j-1)+1)
// 初始值:可以增加一个空串的辅助状态：F(i,0)=i;F(0,j)=j
// 返回结果:F(word1.size(),word2.size())
class Solution {
public:
    /**
     * 
     * @param word1 string字符串 
     * @param word2 string字符串 
     * @return int整型
     */
    int minDistance(string word1, string word2) {
        int row=word1.size();
        int col=word2.size();
        vector<vector<int> > min_distance(row+1,vector<int>(col+1));
        for(int i=0;i<=row;i++)
            min_distance[i][0]=i;
        for(int j=0;j<=col;j++)
            min_distance[0][j]=j;
        for(int i=1;i<=row;i++)
        {
            for(int j=1;j<=col;j++)
            {
                min_distance[i][j]=min(min_distance[i-1][j],min_distance[i][j-1])+1;
                min_distance[i][j]=min((word1[i-1]==word2[j-1]?min_distance[i-1][j-1]:min_distance[i-1][j-1]+1),min_distance[i][j]);
            }
        }
        return min_distance[row][col];
    }
};