面试题 01.05. 一次编辑

字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。 示例 1:

输入: 
first = "pale"
second = "ple"
输出: True

示例 2:

输入: 
first = "pales"
second = "pal"
输出: False

这个题有个相对复杂的思路，就是先求最小编辑距离，然后看是够小于等于1，参考最小编辑距离：

但这个题目是中等题，所以应该可以不这么复杂。经过观察：如果一次编辑可以解决的问题，首先两个字符串长度的差值应该小于等于1，所以：

int n = first.length() - 1;
        int m = second.length() - 1;
        if(Math.abs(m - n) > 1)
        {
          
   
            return false;
        }

除去上述情况后： 我们发现，可以一次编辑的两个字符串的前缀和后缀都是一致的，所以我们使用双指针的思路减去一致的前缀和后缀。 然后判断剩下的字符串： 如果最后剩下的两个字符串的长度差小于等于1则返回真。 具体代码如下：

class Solution {
          
   
    public boolean oneEditAway(String first, String second) {
          
   
        int n = first.length() - 1;
        int m = second.length() - 1;
        if(Math.abs(m - n) > 1)
        {
          
   
            return false;
        }
        boolean ans = true;
        int i = 0 , j = 0;
        while(i <= n && j <= m )
        {
          
   
            if(first.charAt(i) == second.charAt(j))
            {
          
   
                i++;
                j++;
                continue;
            }
            if(first.charAt(n) == second.charAt(m))
            {
          
   
                n--;
                m--;
            }
            else
               break;
        }
        //（i和n； j和m的差值 为0 和-1）
        return (n - i == 0 && m - j == -1) ||   (n - i == -1 && m - j == 0)|| (n - i == 0 && m - j == 0) || (i - n == 1 && j - m == 1);
    }
}

最后返回的状态确实没想到好的表述。