1.5 One Away

There are three types of edits that can be performed on strings: insert a character, remove a character, or replace a character. Given two strings, write a function to check if they are one edit (or zero edits) away.
EXAMPLE
pale, pIe -> true
pales, pale -> true
pale, bale -> true
pale, bake -> false

Hint

• Start with the easy thing. Can you check each of the conditions separately?
• What is the relationship between the "insert character" option and the "remove character" option? Do these need to be two separate checks?
• Can you do all three checks in a single pass?

Solution

本题中定义了对字符串的三种操作：插入一个字符，删除一个字符，替换一个字符。对给定的两个字符串，求出是否可以对其中的一个字符串进行一次（或零次）如上操作便可以得到另一个字符串。

先考虑特殊情况：

• 若两字符串值相等，则不需要进行变换。
• 若两字符串长度差大于1，则必须变换超过1次，直接返回false。

然后再考虑变换1次的情况：

• 若需要插入或者删除操作，说明两字符串长度差必为1，且长串一定包含短串中的所有字符。使用两个指针分别遍历长串和短串，当第一次两个指针对应的字符不同时，说明到达了需要增加（删除）的字符位置，标记一个flag。当发现有第二处不同时，说明需要操作大于1次了，直接返回false。
• 若需要替换操作，说明两字符串长度一定相等，有且仅有1个字符不同。

public boolean oneAway(String s1, String s2) {
    if (s1 == null || s2 == null) return false;
    if (s1.equals(s2)) return true;
    if (Math.abs(s1.length() - s2.length()) > 1) return false;
    
    String shorter = s1.length() > s2.length() ? s2 : s1;
    String longer = s1.length() > s2.length() ? s1 : s2;
    int sIndex = 0, lIndex = 0;
    boolean hasDifference = false;
    while (sIndex < shorter.length() && lIndex < longer.length()) {
        if (shorter.charAt(sIndex) != longer.charAt(lIndex)) {
            if (hasDifference) return false;
            if (shorter.length() == longer.length()) sIndex++;
            hasDifference = true; // 出现了不同，标记
        } else {
            sIndex++; // 短串指针在字符相同时右移，不同时进行判断
        }
        lIndex++; // 长串指针始终右移
    }
    return true;
}