leetcode72. Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

编辑距离是算法导论的一道作业题，不过leetcode的这道题比较简单，权重都一样。

令dp[i][j]代表word1[0..i]和word2[0..j]的编辑距离

则当word1[i]==word[j]时，dp[i][j]=dp[i-1][j-1]

word1[i]!=word[j]时，dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1

class Solution {
public:
    inline bool find(const string &str,char &ch)
    {
        for(char c:str)
        {
            if(c==ch)
                return true;
        }
        return false;
    }
    inline int min(int a,int b,int c)
    {
        if(a<=b &&a<=c)
            return a;
        if(b<=a &&b<=c)
            return b;
        else return c;
    }
    int minDistance(string word1, string word2) {
        int row = word1.length();
        int col = word2.length();
        if(row==0 || col==0)    return row+col;
        vector<vector<int>> dp(row,vector<int>(col,0));//dp[i][j]代表word1[0..i]和word2[0..j]的编辑距离
        //先确定第一行和第一列
        for(int i=0;i<col;i++)
        {
            if(find(word2.substr(0,i+1),word1[0]))
                dp[0][i] = i;
            else
                dp[0][i] = i+1;
        }
        for(int i=1;i<row;i++)
        {
            if(find(word1.substr(0,i+1),word2[0]))
                dp[i][0] = i;
            else
                dp[i][0] = i+1;
        }
        for(int i=1;i<row;i++)
        {
            for(int j=1;j<col;j++)
            {
                if(word1[i] == word2[j])
                    dp[i][j] = dp[i-1][j-1];
                else
                    dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1;
            }
        }
        return dp[row-1][col-1];
    }
};