打开力扣看一道leetcode题目描述，发现力扣中集成了程序面试金典中的题目，一口气刷了4道，直到遇见这道面试题01.05.一次编辑.

暴力求解

我本以为这道题应该也能一遍AC，结果却卡了半个多小时，未能AC的代码如下：

class Solution {
public:
    bool oneEditAway(string first, string second) {
        int m = first.size(),n = second.size();
        //相等返回true
        if(first == second) return true;
        
        //长度相差大于1
        if(abs(m - n) > 1) return false;

        //长度相等,只能有一个不相同
        if(m == n)
        {
            if(m == 1) return true;
            int cnt = 0;
            for(int i = 0;i < m ;i++)
            {   
                if(first[i] != second[i])
                {
                    if(++cnt > 1) return false;
                }
            }
            return true;
        }

        if(abs(m - n ) == 1){
            if(first.find(second) != std::string::npos ||
               second.find(first) !=std::string::npos) {
                return true;   
            }else {
                return false;
            }
        }

        return false;
    }
};

上面的代码可以说是非常直观，问题出在长度差1这种场景，单纯的想到在字符串中查找另一个子串的场景(例如 ab abc,dcba cba)，却不能解决(teacher treacher)这种场景(按照目前只能想到暴力求解)。

1145 / 1146 个通过测试用例
状态：解答错误
提交时间：9 小时前
输入：
"teacher"
"treacher"
输出：false
预期：true

代码写到这里其实内心是有点崩溃的，我们分割问题后，长度相差1这种场景依然和原问题一样难以处理。

双指针解法

看到题解列表标题中有人用双指针方法，这里有个我认为的刷题小tip，当陷入僵局时可以看下题解列表标题，有了思路以后再尝试解决，而不是直接看别人的代码，这样收获会更大一些。

class Solution {
public:
    bool oneEditAway(string first, string second) {
        //相等返回true
        if(first == second) return true;
        
        //长度相差大于1,返回false
        int m = first.size(),n = second.size();
        if(abs(m - n) > 1) return false;
        //长度相差小于等于1
        int l = 0,r1 = m -1,r2 = n - 1;
        while(l <= r1 && l <= r2 && first[l] == second[l]) l++;
        while(r1 >= 0 && r2 >= 0 && first[r1] == second[r2]) {r1--;r2--;}
        if(r1-l < 1 && r2-l < 1) return true;
        
        return false;
    }
};

运行效率:

执行结果：通过
显示详情
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：6.1 MB, 在所有 C++ 提交中击败了90.70%的用户

动态规划

dp[i+1][j+1]表示A的前i个字符与B的前j个字符，如果要通过替换 插入 删除变成一致最少需要的步数时多少?
如果A[i]和B[j]相等，那么dp[i+1][j+1]= dp[i][j];(A的前i个字符要与B的前j个字符变换一致，所需要的最小步骤与A的前i-1个字符和B的前j-1个字符变换需要的步数一致)

如果A[i]和B[j]不相等，这里针对A来说存在三种情况(A[i]前插入 删除A[i] 替换A[i])
替换：dp[i+1][j+1] = dp[i][j] + 1;替换A[i]或B[j]后，只需要计算A的前i-1个字符与B的j-1个最小步数。
删除A[i]: dp[i+1][j+1] = dp[i][j+1] + 1;
A[i]后面插入B[j]:dp[i+1][j+1] =dp[i+1][j] + 1;在原来A[i]后面插入B[j]，dp[i+1][j+1] = dp[i+1][j] + 1.
这里需要解释下，由于已经在A[i]后面插入了B[j],那么此时A[i+1] == B[j]，dp[i+1][j+1] = dp[i+1][j] + 1,这里只要计算A中前i个字符与B中前j-1个字符变成一致需要最少的操作步骤。

class Solution {
public:
    bool oneEditAway(string first, string second) { 
        int m = first.size(),n = second.size();
        int dp[m+1][n+1];
        dp[0][0] = 0;

        //其中一个字符串为空时,更新最小操作次数
        for(int i = 1;i <= m;i++) dp[i][0] = i;
        for(int i = 1;i <= n;i++) dp[0][i] = i;

        for(int i = 0;i < m;i++)
        {
            for(int j = 0;j < n;j++)
            {
                if(first[i] == second[j]) 
                    dp[i+1][j+1] = dp[i][j];
                else 
                    dp[i+1][j+1] = min(min(dp[i][j],dp[i+1][j]),dp[i][j+1]) + 1;
            }
        }
        if(dp[m][n] <= 1) return true;
        return false;
    }
};