一次编辑.md

一次编辑

思路

1. 注释里有我的全部思路，这题提交错了好几次，做的很糟

var oneEditAway = function (first, second) {
  let n1 = first.length
  let n2 = second.length
  if (Math.abs(n1 - n2) > 1) return false
  if (first == second) return true
  if (n1 == n2) {
    //这种情况只能有一个字符不一样，并且注意要顺序一致
    let count = 0
    for (let i = 0; i < n1; i++) {
      if (first[i] != second[i]) count++
    }
    return count == 1
  }
  if ((n1 == 0 && n2 == 1) || (n1 == 1 && n2 == 0)) return true
  if (n1 < n2) {
    for (let i = 0; i < n1; i++) {
      if (first[i] != second[i]) {
        //发现了不一样的地方
        second = second.replace(second[i], '')
        return first == second
      }
    }
    return true
  }
  if (n2 < n1) {
    for (let i = 0; i < n2; i++) {
      if (first[i] != second[i]) {
        //发现了不一样的地方
        first = first.replace(first[i], '')
        return first == second
      }
    }
    return true
  }
  // return false
}

题解里看到的: https://leetcode-cn.com/problems/one-away-lcci/solution/shu-ju-jie-gou-he-suan-fa-duo-chong-shi-kdo7j/

2. 给一次试错的机会，如果一次匹配失败我们还要继续匹配，如果再次失败就返回 false。整个匹配下来如果只失败一次或者没有失败，返回 true。

    public boolean oneEditAway(String first, String second) {
        int length1 = first.length();
        int length2 = second.length();
        //因为只有一次编辑的机会，如果两个字符串长度相差大于1，
        //直接返回false
        if (Math.abs(length1 - length2) > 1)
            return false;
        //给他一次不匹配的机会
        boolean noMatch = true;
        for (int i = 0, j = 0; i < length1 && j < length2; ) {
            //两个字符串从前往后开始遍历，如果字符一样就继续比较下一个
            if (first.charAt(i++) == second.charAt(j++))
                continue;
            //走到这一步，说明不匹配了，如果之前有一次匹配失败，
            // 直接返回false
            if (!noMatch)
                return false;
            //第一次匹配失败，给他一次机会
            noMatch = false;
            //如果这两个字符串不相等，说明他们一个长一个短，短的往前
            //挪一步，他俩在继续匹配
            if (length1 != length2) {
                if (length1 > length2)
                    j--;
                else
                    i--;
            }
        }
        return true;
    }

3. 这个应该最好理解，如果匹配失败，我们只需要比较后面的字符串相等即可，来看下代码

    public boolean oneEditAway(String first, String second) {
        int length1 = first.length();
        int length2 = second.length();
        //因为只有一次编辑的机会，如果两个字符串长度相差大于1，
        //直接返回false
        if (Math.abs(length1 - length2) > 1)
            return false;
        for (int i = 0, j = 0; i < length1 && j < length2; ) {
            //匹配成功就继续
            if (first.charAt(i++) == second.charAt(j++))
                continue;
            //到这里说明匹配失败了

            //失败之后会有3种情况，
            // 如果这两个字符串相等，从他们的下一个开始比较。
            // 如果first比second长，就把first截取一位和second比较
            // 如果second比first长，就把second截取一位和first比较
            if (length1 == length2)
                return first.substring(i).equals(second.substring(i));
            if (length1 > length2)
                return first.substring(i).equals(second.substring(i - 1));
            return first.substring(i - 1).equals(second.substring(i));
        }
        return true;
    }

4. 动态规划

这题可以参照编辑距离写的题解，第 72 题要求的是编辑距离，我们这里也要使用第 72 题的答案，直接判断最后的编辑距离是否小于等于 1 即可，具体分析就不在写了，我们来看下代码

public static boolean oneEditAway(String word1, String word2) {
        int length1 = word1.length();
        int length2 = word2.length();
        int dp[][] = new int[length1 + 1][length2 + 1];
        for (int i = 0; i <= length1; i++) {
            dp[i][0] = i;//边界条件，相当于word1的删除操作
        }
        for (int i = 0; i <= length2; i++) {
            dp[0][i] = i;//边界条件，相当于word1的添加操作
        }
        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= length2; j++) {//下面是上面分析的递推公式
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }
        return dp[length1][length2] <= 1;
    }