题目
字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。
示例 1:
输入: first = "pale" second = "ple" 输出: True
示例 2:
输入: first = "pales" second = "pal" 输出: False
解题
方法一：(动态规划)使用编辑距离
使用leetcode-72：编辑距离来做本题
判断编辑距离<=1即可。
但显然，这不是最优解，这道题没有那么复杂。
class Solution { public: bool oneEditAway(string first, string second) { int m=first.size(); int n=second.size(); vector<vector<int>> dp(m+1,vector<int>(n+1)); for(int i=0;i<=m;i++) dp[i][0]=i; for(int j=0;j<=n;j++) dp[0][j]=j; for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ if(first[i-1]==second[j-1]){ dp[i][j]=dp[i-1][j-1]; } else{ dp[i][j]=min({dp[i][j-1],dp[i-1][j],dp[i-1][j-1]})+1; } } } return dp[m][n]<=1; } };
方法二：双指针
class Solution { public: bool oneEditAway(string first, string second) { int lf=first.size();//length first int ls=second.size();//length second if(lf>ls){ return oneEditAway(second,first);//通过这一步保证，second长度大于first } if(ls-lf>1) return false; else if(ls==lf){ int count=0; for(int i=0;i<ls;i++){ if(first[i]!=second[i]) count++; } return count<=1; } else if(ls-lf==1){ int i=0,j=0; while(i<lf){ if(first[i]!=second[j]){ j++; if(j-i>1) return false; } else{ i++; j++; } } } return true; } };
