面试题 01.05. 一次编辑

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

示例 1:

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

示例 2:

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

解题方法:

动态规划法:

• 找出最小编辑次数(dp[i][j]的含义)
• 初始化(一边的字符串为空):
  • dp[0][j] = j;
  • dp[0][i] = i;
• 动态转化方程
  • 如果当前字符相等,就等于前一个字符的编辑次数(次数不变)
  • 如果不相等,就等于前一个字符的最小编辑次数 + 1
• 时间复杂度O(nm)

class Solution {
public:
    bool oneEditAway(string first, string second) 
    {
        int n = first.size();
        int m = second.size();
        if(n - m > 1)
            return false;
        vector<vector<int>> dp(n + 1,vector<int>(m + 1,0));

        //当第一个字符串为""
        for (int j = 1; j <= m; j++) {

            dp[0][j] = j;
        }
        //当第二个字符串为""
        for (int i = 1; i <= n; i++) 
        {
            dp[i][0] = i;
        }

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

        int SizeMax = max(n,m);
        if(dp[n][m] > 1)
            return false;
        return true; 
    }
};

双指针(推荐)

• 判断字符串长度
  • 如果大于1就说明无法一次编辑实现
  • 如果等于1,说明第一个比第二个长,在second上需要加一个字符(加减是一样的)
  • 如果小于1,说明第一个比第二个断,在second上需要减一个字符
  • 如果等于0,说明需要改变second上的字符.
• 同时遍历两个字符串,如果不同就根据情况编辑,记录编辑次数.如果大于1就返回false;
• 时间复杂度O(max(n,m))

class Solution {
public:
    bool oneEditAway(string first, string second) {
        int n = first.size();
        int m = second.size();
        int len = n-m;	
	    if (abs(len) > 1)
		    return false;
	    int count=1;
	    for (int i = 0,j=0; i < n &&j < m; i++,j++) 
        {
		    if (first[i]!=second[j]) {
		    	if (len==1) //second添加一个字符 
			    	j--;
                else if (len==-1) //second删除一个字符
		    		i--;
		    	count--;    //编辑second的字符
	    	}
	    	if (count<0)     //大于一次编辑就失败
		    	return false;
    	}
    	return true;   
    }
};