161.One Edit Distance

Link

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

Example 1:

Input: s = "aDb", t = "adb" 
Output: true

Example 2:

Input: s = "ab", t = "ab" 
Output: false
Explanation:
s=t ,so they aren't one edit distance apart

Example 3:

Input: s = "1203", t = "1213"
Output: true
Explanation: We can replace '0' with '1' to get t.

Solution

當char[i] != char[j]時只會三種狀況讓editdistance是1

1. abd, bd

s.substring(i + 1).equals(t.substring(j))

2. ad, cad

s.substring(i).equals(t.substring(j + 1))

3. acd, ecd

s.substring(i+1).equals(t.substring(j + 1))

public boolean isOneEditDistance(String s, String t) {
    if(s==null || t==null)
        return false;
 
    int m = s.length();
    int n = t.length();
 
    if(Math.abs(m-n)>1){
        return false;
    }
 
    int i=0; 
    int j=0; 
    int count=0;
 
    while(i<m&&j<n){
        if(s.charAt(i)==t.charAt(j)){
            i++;
            j++;
        }else{
            count++;
            if(count>1)
                return false;
 
            if(m>n){
                i++;
            }else if(m<n){
                j++;
            }else{
                i++;
                j++;
            }
        }
    }
 
    if(i<m||j<n){
        count++;
    }
 
    if(count==1)
        return true;
 
    return false;
}