20ms c++ solution Easy to understand


  • 0
    C
    int minDistance(string word1, string word2) {
        int w1l = word1.length();
        int w2l = word2.length();
        
        int d[w1l + 1][w2l + 1];
        
        for(int i = 0; i < w1l + 1; i++)
        {
            d[i][0] = i;// attention: d[i][j] ~ minimum edit distance for word1[0 ... i - 1] word2[0 ... j - 1]
        }
        
        for(int j = 0; j < w2l + 1; j++)
        {
            d[0][j] = j;
        }
        
        for(int i = 1; i < w1l + 1; i++)
        {
            for(int j = 1; j < w2l + 1; j++)
            {
                if(word1[i - 1] == word2[j - 1])
                {
                    d[i][j] = min(min(d[i - 1][j - 1], d[i - 1][j] + 1), d[i][j - 1] + 1);
                }
                else
                {
                    d[i][j] = min(min(d[i - 1][j - 1], d[i - 1][j]), d[i][j - 1]) + 1;
                }
            }
        }
        
        return d[w1l][ w2l];
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.