20ms DP solution C++

  • 2
    class Solution {
    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 {
    return step[l1][l2];

Log in to reply

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