One Away LCCI 一次编辑

问题描述：

有2个字符串s1,s2,对于字符串有3种操作，插入，删除，修改。
现在要判断这2个字符串s1,s2,是否可以通过一次编辑或者0次，达到相等。

分析

要达到相等，首先长度就不能相差>1.
如果原来2个字符串就equal，可以直接返回。
到此，2个字符串长度相差<=1,并且不相等。
使用cnt作为编辑的计数，如果i和j分别是2个字符串的指针。
1 s1[i]==s2[j]，说明2个字符相等，同时后移1位。

2 s1[i]!=s2[j],说明字符不相等，必然要进行编辑，但是有3种，insert，del，update,如果2个字符串长度一样即n==m,那么就只能选择update，cnt+=1。
如果n!=m,那么较短的一侧可以选择增加一位用来匹配，然后2者后移，cnt+=1。当然也可以选择较长的减少一位，cnt+=1。
假设较长字符串longer，较短字符串shorter，
假设i是shorter的指针，j是longer的指针，并且n!=m,那么增加较短的字符串，i就保持不变，j++,如果是删除j位置的字符，i不变，j++
最后遍历完成后，cnt<=1说明true。

其实如果满足一次编辑，在n!=m的情况下，比然要满足，longer中的位置 p，0_{p-1与shorter的0}p-1相等，即前缀一样，并且在 shorter[p_{n]==longer[p+1}m],即后缀一样。

代码

时间复杂度 O(N ),空间复杂度 O(1)

public boolean oneEditAway(String a, String b) {
        int n = a.length(), m = b.length();
        if (Math.abs(n - m) > 1) return false;
        if (n > m) return oneEditAway(b, a);
        int i = 0, j = 0, cnt = 0;
        while (i < n && j < m && cnt <= 1) {
            char c1 = a.charAt(i), c2 = b.charAt(j);
            if (c1 == c2) {
                i++; j++;
            } else {
                if (n == m) {
                    i++; j++; cnt++;
                } else {
                    j++; cnt++;
                }
            }
        }
        return cnt <= 1;
    }

代码是抄 宫水 大佬的，写的太优雅。

Tag

双指针