161. One Edit Distance ---------M

Given two strings s and t, return true if they are both one edit distance apart, otherwise return false.

A string s is said to be one distance apart from a string t if you can:

• Insert exactly one character into s to get t.
• Delete exactly one character from s to get t.
• Replace exactly one character of s with a different character to get t.

 

Example 1:

Input: s = "ab", t = "acb"
Output: true
Explanation: We can insert 'c' into s to get t.

Example 2:

Input: s = "", t = ""
Output: false
Explanation: We cannot get t from s by only one step.

Example 3:

Input: s = "a", t = ""
Output: true

Example 4:

Input: s = "", t = "A"
Output: true

 

Constraints:

• 0 <= s.length <= 104
• 0 <= t.length <= 104
• s and t consist of lower-case letters, upper-case letters and/or digits.

A:


*************递归*****************

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        int n1 = s.length();
        int n2 = t.length();
        if(n1 > n2)
            return isOneEditDistance(t,s);
        if(n1==0){
            return n2==1;
        }
        if(s[0]==t[0]){
            return isOneEditDistance(s.substr(1), t.substr(1));
        }else{ // not equal
            if(n1==n2) // replace on first
                return s.substr(1) == t.substr(1);
            else // remove the first of longer
                return s == t.substr(1);
        }
    }
};

不用递归，  直接用两个指针， 这样快一些。

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        int n1 = s.length();
        int n2 = t.length();
        if(n1 > n2)
            return isOneEditDistance(t,s);
        if(n1+1<n2)
            return false;        
        for(int is = 0; is<n1;is++){
            if( s[is] != t[is]){
                if(n1==n2)
                    return s.substr(is+1) == t.substr(is+1);
                else
                    return s.substr(is) == t.substr(is+1);
            }
        }
        return n1+1==n2;// for case s="ab"  t="abc"
    }
};

就是简单的分情况讨论

public class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int n1 = s.length(), n2 = t.length();
        if( n1< n2)
            return n1+1 == n2 && delOneStep(t,s);
        else if(n1 == n2)
            return changeOneStep(s,t);
        else return n1-1 == n2 && delOneStep(s,t);
    }
    private boolean changeOneStep(String s, String t){
        int nDif = 0;
        for(int i =0;i<s.length();i++){
            if(s.charAt(i) != t.charAt(i))
                nDif++;
        }
        return nDif==1;
    }
    private boolean delOneStep(String sLong, String sShort){
        int dif = 0;
        for(int i = 0;i<sShort.length();i++){
            if(sShort.charAt(i)!=sLong.charAt(i+dif)){
                if(dif!=0)
                    return false;
                i--;
                dif=1;
            }
        }
        return true;
    }
}

Mistakes: