LeetCode刷题【面试题 01.05】一次编辑

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

示例 1:

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

示例 2:

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

简单做下，逐字符比较法，附加动态规划相关

简单做下，和另外一题几乎一毛一样
161. 相隔为 1 的编辑距离

这题包含了两字符相同的情况也返回true,稍微更加简单点

另外一题的题解 简单逐字符比较，方法也几乎一样

本题就直接比较遍历最后的指针所在位置了，没有去额外声明变量统计相同字符数量，因为在遍历的过程中其实已经代表了有多少个字符相同了

代码

class Solution {
    public boolean oneEditAway(String first, String second) {
        //相同字符的直接返回
        if (first.equals(second)){
            return true;
        }
        //字符长度相差超过一个的
        if (Math.abs(first.length() - second.length()) > 1){
            return false;
        }
        if (first.length() == second.length()){
            int idx = -1;
            while (++idx < first.length() && first.charAt(idx) == second.charAt(idx)){}
            while (++idx < first.length() && first.charAt(idx) == second.charAt(idx)){}
            return idx == first.length();
        }
        if (first.length()>second.length()){
            if (second.length()==0){
                return true;
            }
            int fIdx = 0;
            int sIdx = 0;
            while (sIdx < second.length() && first.charAt(fIdx) == second.charAt(sIdx)){
                fIdx++;
                sIdx++;
            }
            fIdx++;
            while (sIdx < second.length() && first.charAt(fIdx) == second.charAt(sIdx)){
                fIdx++;
                sIdx++;
            }
            return fIdx == first.length();
        }else{
            return oneEditAway(second,first);
        }
    }
}

动态规划 其实也能做，不过单就这题的话，有点杀鸡用牛刀的意思了
可以想试试动态规划的话看下72. 编辑距离

我之前写过的题解 配有详细画图说明 【动态规划】java 编辑距离