[LeetCode 161] One Edit Distance

Given two strings s and t, determine if they are both one edit distance apart.

Note:

There are 3 possiblities to satisify one edit distance apart:

• Insert a character into s to get t
• Delete a character from s to get t
• Replace a character of s 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 = "cab", t = "ad"
Output: false
Explanation: We cannot get t from s by only one step.

Example 3:

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

Solution: 分类处理

1. 如果2个字符串的长度差 > 1，那么不可能是one edit distance，直接返回false
2. 如果2个字符串的长度差 == 0，遍历两个字符串，计算有多少个不同的字符。只有count == 1时，才是one edit distance。 Note两个相同的String，不是one edit distance。

if (shorter.charAt (i) != longer.charAt (i))
    count ++;

3. 如果2个字符串的长度差 == 1，那么longer string去掉那个不相同的就应该等于shorter string。 如果不等，不是one edit distance。

Code

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        if ((s == null || s.length () == 0) && (t == null || t.length () == 0))
            return false;
        
        String shorter = s.length () <= t.length () ? s : t;
        String longer = s.length () > t.length () ? s : t;
        
        int lenDiff = longer.length () - shorter.length ();
        
        if (lenDiff > 1) {
            return false;
        }
        else if (lenDiff == 0) {
            int count = 0;
            for (int i = 0; i < shorter.length (); i++) {
                if (shorter.charAt (i) != longer.charAt (i))
                    count ++;
            }
            
            return count == 1;
        } else if (lenDiff == 1) {
            for (int i = 0; i < shorter.length (); i++) {
                if (longer.charAt (i) != shorter.charAt (i)) {
                    if (i == 0) {
                        String deleteOne = longer.substring (i + 1, longer.length ());
                        return deleteOne.equals (shorter);
                    } else {
                        String deleteOne = longer.substring (0, i) + longer.substring (i + 1, longer.length ());
                        return deleteOne.equals (shorter);
                    }
                }
            }
            
            return true;
        }
        
        return false;
    }
}