【步伐员面试金典】面试题 01.05. 一次编辑

题目描述

描述：字符串有三种编辑操作:插入一个英笔墨符、删除一个英笔墨符大概替换一个英笔墨符。 给定两个字符串，编写一个函数判断它们是否只需要一次(大概零次)编辑。

1. 输入:
2. first = "pale"
3. second = "ple"
4. 输出: True

复制代码

1. 输入:
2. first = "pales"
3. second = "pal"
4. 输出: False

复制代码

解题思路

思路1：最直观的想法是，动态规划系列编辑间隔问题，判断编辑间隔是否小于等于1。其中dp[j]表示以first[i-1]末端转换为以second[j-1]末端所需的最少次数，其递推公式为：假如first[i-1]=second[j-1]，则dp[j]=dp[i-1][j-1]，反之不相等则dp[j]=min({dp[j-1],dp[i-1][j],dp[i-1][j-1]})+1。

1.     bool oneEditAway(string first, string second) {
2.         int n1=first.size();
3.         int n2=second.size();
4.         //dp[i][j]表示first[i-1]变成second[j-1]次数
5.         vector<vector<int>> dp(n1+1,vector<int>(n2+1,0));
6.         // second为空串
7.         for(int i=0;i<n1;i++) dp[i][0]=i;
8.         // first为空串
9.         for(int i=0;i<n2;i++) dp[0][i]=i;
10.         for(int i=1;i<=n1;i++)
11.         {
12.             for(int j=1;j<=n2;j++)
13.             {
14.                 if(first[i-1]==second[j-1])
15.                     dp[i][j]=dp[i-1][j-1];
16.                 else
17.                     dp[i][j]=min({dp[i][j-1],dp[i-1][j],dp[i-1][j-1]})+1;
18.             }
19.         }
20.         return dp[n1][n2]<=1;
21.     }

复制代码

思路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，则不可以一次编辑完成，反之可以。

1. // 不可以处理长度相同的两个字符串 ab和bc无法判断
2. bool oneInsert(string longer,string shorter)
3. {
4.     int n1=longer.size();
5.     int n2=shorter.size();
6.     int index1=0;
7.     int index2=0;
8.     while(index1<n1&&index2<n2)
9.     {
10.         // 相等两者均后移
11.         if(longer[index1]==shorter[index2])
12.         {
13.             index1++;
14.             index2++;
15.         }
16.         // 不相等长串后移
17.         else
18.             index1++;
19.         // 相差大于1不可以一次编辑
20.         if(index1-index2>1)
21.             return false;
22.     }
23.     return true;
24. }
25. bool oneEditAway(string first, string second)
26. {
27.     int n1=first.size();
28.     int n2=second.size();
29.     // 长度相差大于1则不可以一次编辑完成
30.     if(abs(n1-n2)>1) return false;
31.     int diff=n1-n2;
32.     // 删除
33.     if(diff==1)
34.         return oneInsert(first,second);
35.     // 增加
36.     else if(diff==-1)
37.         return oneInsert(second,first);
38.     // 替换或者相同  ab bc
39.     int num=0;
40.     for(int i=0;i<n1;i++)
41.     {
42.         if(first[i]!=second[i])
43.         {
44.             num++;
45.             // 有两个或者两个以上不同则不可以一次编辑完成
46.             if(num>1) return false;
47.         }
48.     }
49.     return true;
50. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。