【步伐员面试金典】面试题 01.05. 一次编辑
题目描述描述：字符串有三种编辑操作:插入一个英笔墨符、删除一个英笔墨符大概替换一个英笔墨符。 给定两个字符串，编写一个函数判断它们是否只需要一次(大概零次)编辑。
输入:
first = "pale"
second = "ple"
输出: True
输入:
first = "pales"
second = "pal"
输出: False
解题思路
思路1：最直观的想法是，动态规划系列编辑间隔问题，判断编辑间隔是否小于等于1。其中dp表示以first末端转换为以second末端所需的最少次数，其递推公式为：假如first=second，则dp=dp，反之不相等则dp=min({dp,dp,dp})+1。
bool oneEditAway(string first, string second) {
int n1=first.size();
int n2=second.size();
//dp表示first变成second次数
vector<vector<int>> dp(n1+1,vector<int>(n2+1,0));
// second为空串
for(int i=0;i<n1;i++) dp=i;
// first为空串
for(int i=0;i<n2;i++) dp=i;
for(int i=1;i<=n1;i++)
{
for(int j=1;j<=n2;j++)
{
if(first==second)
dp=dp;
else
dp=min({dp,dp,dp})+1;
}
}
return dp<=1;
}
思路2：假设first长度为n1，second长度为n2，则一次编辑有三种情况：第一种是n1=n2，即first需要替换一个字符才华变成second；第二种是n1-n2=1，即first需要删除一个字符才华变成second；第三种是n2-n1=1，即first需要添加一个字符才华变成second；零次编辑有一种情况：即n1=n2且first与second完全相同。首先盘算first和second的长度，并根据两者之间的长度关系来进行相应的处理。假如两者长度相同，则遍历字符串并逐个比较当前元素，再记载不同元素的个数，假如其大于1，则不可以一次编辑完成，反之可以；假如两者长度相差为1，则记载长串为longer，记载短串为shorter，利用双指针遍历两个字符串，假如相同则两个指针均后移，反之只将长串指针后移，假如长串与短串指针相差大于1，则不可以一次编辑完成，反之可以。
// 不可以处理长度相同的两个字符串 ab和bc无法判断
bool oneInsert(string longer,string shorter)
{
int n1=longer.size();
int n2=shorter.size();
int index1=0;
int index2=0;
while(index1<n1&&index2<n2)
{
// 相等两者均后移
if(longer==shorter)
{
index1++;
index2++;
}
// 不相等长串后移
else
index1++;
// 相差大于1不可以一次编辑
if(index1-index2>1)
return false;
}
return true;
}
bool oneEditAway(string first, string second)
{
int n1=first.size();
int n2=second.size();
// 长度相差大于1则不可以一次编辑完成
if(abs(n1-n2)>1) return false;
int diff=n1-n2;
// 删除
if(diff==1)
return oneInsert(first,second);
// 增加
else if(diff==-1)
return oneInsert(second,first);
// 替换或者相同ab bc
int num=0;
for(int i=0;i<n1;i++)
{
if(first!=second)
{
num++;
// 有两个或者两个以上不同则不可以一次编辑完成
if(num>1) return false;
}
}
return true;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]