C++_Accepted_(& 72. Edit Distance)


  • 0
    class Solution {
    public:
    bool isOneEditDistance(string s, string t) {
        int n1 = s.size();
        int n2 = t.size();
        if(abs(n1 - n2) >= 2) return false;
        if(n1 == n2){
            int k = 0;
            for(int i = 0; i < n1; ++i){
                if(s[i] != t[i]){
                    k++;
                    if(k >= 2) return false;
                }
            }
            if(k == 0) return false;
        }
        else{
            if(n1 < n2){swap(n1,n2); swap(s,t);}
            int k = 0;
            for(int i = 0, j = 0; i < n1 && j < n2;){
                if(s[i] != t[j]){
                    i++;
                    k++;
                    if(k >= 2) return false;
                }else{
                    i++;
                    j++;
                }
            }
            if(k >= 2) return false;
        }
        return true;
    }
    };
    

    class Solution {
    public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        int res[m + 1][n + 1];
        res[0][0] = 0;
        for(int i = 1; i < m + 1; ++i){
            res[i][0] = i;
        }
        for(int j = 1; j < n + 1; ++j){
            res[0][j] = j;
        }
        
        for(int i = 1; i < m+1; ++i){
            for(int j = 1; j < n+1; ++j){
                if(word1[i-1] == word2[j-1]){
                    res[i][j] = res[i-1][j-1];
                }else{
                    res[i][j] = min(res[i-1][j], min(res[i][j-1],res[i-1][j-1])) + 1;
                }
            }
        }
        return res[m][n];
    }
    };

Log in to reply
 

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