Very quick solution C++


  • 0
    S
    class Solution {
    public:
        int minDistance(string word1, string word2) {
            if(word1.empty()) return word2.length();
            if(word2.empty()) return word1.length();
            int len1 = word1.length(), len2 = word2.length();
            int distance[len1+1][len2+1];
            memset(distance, 0, sizeof(int)*(len1+1)*(len2+1));
            for(int i = 0; i <= len1; ++i) distance[i][0] = i;
            for(int i = 0; i <= len2; ++i) distance[0][i] = i;
            for(int i = 1; i <= len1; ++i){
                for(int j = 1; j <= len2; ++j){
                    if(word1[i-1] == word2[j-1]) distance[i][j] = distance[i-1][j-1];
                    else distance[i][j] = min(distance[i-1][j], min(distance[i][j-1], distance[i-1][j-1]))+1;
                }
            }
            return distance[len1][len2];
        }
    };
    

Log in to reply
 

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