LeetCode——面试题 01.05. 一次编辑

通过万岁！！！

• 题目：就是给你两个字符串，然后看看两个字符串能不能通过操作一个字符，让两个字符串相同，操作可以是一次替换、或者一次删除、或者一次添加。
• 思路：首先，如果两个字符串的长度差距大于1，那肯定不行，直接返回，然后两个字符串长度相同，则只能用替换操作，也就是只能由一个字符不同。如果长度差距是1，则我们遇到不同的时候，让短的停留，长度继续下一个字符即可，然后保证下面的都一样即可。
• 技巧：就是遍历一下就行了。这里需要注意，我们最好是确定一下让一个字符串长度是长的那个。

java代码

class Solution {
    public boolean oneEditAway(String first, String second) {
        int flen = first.length(), slen = second.length();
        if (Math.abs(flen - slen) >= 2) return false;
        if (flen < slen) {// 保证first是长的
            return oneEditAway(second, first);
        }
        if (slen == 0) return true;
        if (flen == slen) {// 替换操作
            boolean flag = false;
            for (int i = 0; i < flen; i++) {
                if (first.charAt(i) != second.charAt(i)) {
                    if (!flag) {// 第一次遇到不合适的
                        flag = true;
                    } else {// 第二次了
                        return false;
                    }
                }
            }
            return true;
        } else {// 删除操作，这时候flen-slen=1
            boolean flag = false;
            for (int i = 0, j = 0; i < flen && j < slen; i++, j++) {
                if (first.charAt(i) != second.charAt(j)) {
                    j--;// 保证j原地不动
                    if (!flag) {
                        flag = true;
                    } else {
                        return false;
                    }
                }
            }
            return true;
        }
    }
}

• 总结：题目不是很难，主要是找到规律。关于删除和添加，其实是一个操作，因为意义一样，我将长的删除掉一个，跟我对短的添加一个，是一样的。