一、题目描述

二、解题思路

  两个字符串的编辑距离咱们就当作是把 s 变为 t 须要执行多少次操做，能够选择的操做有：java

  一、插入字符
  二、删除字符
  三、替换字符web

  那咱们如何来使得 s 变为 t 呢？svg

  假设 s = “1203”，t = “1213a”，定义两个指针分别指向两个字符串的末尾：

  如今两个字符不相同，咱们能够选择的操做有：spa

  一、在 ‘3’ 后面插入 ‘a’；
  二、把 ‘3’ 变为 ‘a’；
  三、把 ‘3’ 给删除了。3d

  假设我选择的是插入操做，结果为：

  插入完毕，i 不变（由于没有对 i 位置进行什么操做），j 往前走一步：

  两个字符相等，因而什么都不用作，两个指针往前走：

  两个字符又不相等，我又有三种操做能够选择，此时我选择替换：

  接着两个指针继续往前走，直到两个指针都指向 -1 ，编辑结束。指针

  总结上面，我总共执行了 2 次操做，第一次是插入，第二次是替换。编辑距离为 2。code

  很明显，只要我中间字符不相等时选择的操做不一样，都会影响后面的操做，也就是说，不止一个编辑距离。xml

  s 转为 t 和 t 转为 s 的全部编辑距离应该是同样的。blog

  如今题目问：字符串 s 转为 t 的编辑距离是否为 1。token

  咱们经过上面的分析可知，编辑距离不止一个，其实就是问，最小编辑距离是否为 1 （若是两个字符串同样，编辑距离为 0）.

  很明显这是一个动态规划问题。

  设 dp[i][j] 表示字符串 s 的前 i 个字符转换为 t 的前 j 个字符的最小编辑距离。

  若是 s.charAt(i-1) == t.charAt(j)，说明最后一个字符同样，什么都不用作，问题等价于 dp[i-1][j-1]。

  若是 s.charAt(i-1) != t.charAt(j)，则咱们有三种操做：

  一、s.charAt(i-1) 后面插入字符，结果等价于 dp[i][j-1] + 1
  二、s.charAt(i-1) 删除掉，结果等价于 dp[i-1][j] + 1
  三、s.charAt(i-1) 替换为 t.charAt(j)，结果等价于 dp[i-1][k-1] + 1

  选哪一个呢？确定选择值最小的那个啦~

三、解题代码

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int len1 = s.length();
        int len2 = t.length();
        if (len1 == 0) return len2 == 1;
        if (len2 == 0) return len1 == 1;
        // dp[i][j] 表示 s 的前 i 个字符变为 t 的前 j 个字符的编辑路径
        int[][] dp = new int[len1 + 1][len2 + 1];
        // j 没有字符，那么 i 有多少个就删除多少次
        for (int i = 1; i <= len1; i++) dp[i][0] = i;
        // i 没有字符，那么 j 有多少个就插入多少次
        for (int j = 1; j <= len2; j++) dp[0][j] = j;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (s.charAt(i-1) == t.charAt(j-1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(Math.min(
                            dp[i][j - 1] + 1,   // 插入
                            dp[i - 1][j] + 1),        // 删除
                            dp[i - 1][j - 1] + 1);    // 替换
                }
            }
        }
        return dp[len1][len2] == 1;
    }
}