20ms DP solution C++


  • 2
    class Solution {
    public:
    int minDistance(string word1, string word2) {
        if (word1.empty()) return word2.size();
        if (word2.empty()) return word1.size();
        int l1 = word1.size(),l2 = word2.size();
        int step[l1+1][l2+1];
        for (int i=0;i<=l2;i++) step[0][i] = i;
        for (int i=1;i<=l1;i++) step[i][0] = i;
        for (int i=1;i<=l1;i++){
            for (int j=1;j<=l2;j++){
                if (word1[i-1]==word2[j-1]) step[i][j]=step[i-1][j-1];
                else {
                    step[i][j]=min(min(step[i-1][j-1],step[i-1][j]),step[i][j-1])+1;
                }
            }
        }
    return step[l1][l2];
    }
    };

Log in to reply
 

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