面试金典0105 一次编辑

题目：一次编辑

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

  # 示例 1:
  输入: 
  first = "pale"
  second = "ple"
  输出: True
      
  # 示例 2:
  输入: 
  first = "pales"
  second = "pal"
  输出: False

解题方法：

1. 分情况讨论：
   1. 当两字符串长度相差大于1时：不可能
   2. 当两字符串长度相等时：判断替换次数是否小于等于一
   3. 当两字符串长度相差为1时：遍历长的，看短的是否能只用一次插入就完成

目前只有一种解决方案，时间复杂度为O(n)，空间复杂度为​O(n)​

解法一：

巧妙的点在于当长度相差1时，可以再次调用函数，传入参数时将first和second对调即可

#include<cmath>

class Solution {
public:
    bool oneEditAway(string first, string second) 
    {
        if(first == second) // 相等
            return true;
        if(first.size() == second.size()) // 不相等，但长度相等，判断替换策略是否可行
        {
            int flag = 0;
            for(int i=0; i<first.size(); ++i)
            {
                if(first[i] != second[i])
                {
                    flag++;
                }
            }
            return flag <= 1;
        }
        if((first.size() - second.size()) == 1) // 不相等，长度差一，判断添加策略是否可行
        {
            bool flag = false;
            for(int i=0, j=0; i<first.size(); ++i, ++j) // 注意遍历较长的字符串
            {
                // cout << i << "  "<< j << endl;
                if(first[i] != second[j])
                {
                    if(flag)
                    {
                        return false;
                    }
                    flag = true;
                    --j;
                }
            }
            return true;
        }
        if((first.size() - second.size()) == -1) // 不相等，长度差一，判断添加策略是否可行
        {
            return oneEditAway(second, first); // 聪明的switch
        }
        return false;
    }
};