[leetcode] One Edit Distance


One Edit Distance

Given two strings S and T, determine if they are both one edit distance apart.

two pointers.

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        int ls = s.size();
        int lt = t.size();
        if(abs(ls - lt) > 1) return false;
        int i = 0, j = 0;
        int dist = 0;
        while(i < ls && j < lt){
            if(s[i] != t[j]){
                dist++;
                if(dist > 1) break;
                if(ls > lt){
                    j--; // do not move j
                }
                else if(ls < lt){
                    i--; // do not move i
                }
            }
            i++;
            j++;
        }
        // dist == 1 or only the last character is different.
        return dist == 1 || (dist == 0 && ls != lt);
    }
};

 

 

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        int distance = 0;
        string tmp = s;
        if(s.size() > t.size()){
            s = t;
            t = tmp;
        }
        if(t.size() - s.size() > 1) return false;
        // replace
        if(s.size() == t.size()){
            for(int i = 0; i < s.size(); i++){
                if(s[i] != t[i]){
                    distance++;
                }
            }
            return distance == 1;
        }
        
        // s is shorter than t
        if(s.size() == 0) return true;
        for(int i = 0; i < s.size(); i++){
            if(s[i] != t[i]){
                t.erase(i, 1);
                i--;
                distance++;
            }
            if(distance > 1){
                break;
            }
        }
        return distance == 1 || distance == 0;
    }
};

 

Leave a comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.