做了这么久的每日一题，第一次碰到面试题hhh
本文首发于馆主君晓的博客，05-13
题目内容
?题目链接，面试题 01.05. 一次编辑，题目截图如下：
题目分析
??还是老规矩，我们首先来解读一下题目，题目的意思就是给你两个字符串，然后你判断能不能通过一次编辑，将一个字符串变成另外一个字符串。其中，一次编辑的意思是，只进行一次插入、删除、修改操作。读完题目之后，其实就好说了，我们做一个简单的分类讨论即可。
- 当两个字符的长度之差的绝对值大于2，返回false。
- 当两个字符的长度相等，判断有几个不一样的字符，大于1的返回false，否则返回true。
- 当两个字符的长度差的绝对值为1，那么我们就对长的字符去枚举要删除字符的位置，一旦子字符串与短字符串相等，那么返回true，否则返回false。
代码实现
??两种方式的c++代码实现如下：
class Solution {
public:
bool oneEditAway(string first, string second) {
int length_1 = first.length();
int length_2 = second.length();
if(abs(length_1-length_2)>=2){
return false;
}
if(length_1==length_2){
// 长度完全相等 那就修改即可
int count = 0;
for(int i = 0;i<length_1;i++){
if(first[i]!=second[i]){
count++;
if(count>=2){
return false;
}
}
}
return true;
}
// 此时就是长度差一个
if(length_1>length_2){
// 枚举 first长度为 length_1-1的子字符串
for(int i = 0;i<length_1;i++){
string tmp;
if(i==0){
tmp = first.substr(1,length_1-1);
}else if(i==length_1-1){
tmp = first.substr(0,length_1-1);
}else{
tmp = first.substr(0,i)+first.substr(i+1,length_1-i-1);
}
if(tmp==second){
return true;
}
}
}else{
// 枚举 second长度为 length_2-1的子字符串
for(int i = 0;i<length_2;i++){
string tmp;
if(i==0){
tmp = second.substr(1,length_2-1);
}else if(i==length_2-1){
tmp = second.substr(0,length_2-1);
}else{
tmp = second.substr(0,i)+second.substr(i+1,length_2-i-1);
}
if(tmp==first){
return true;
}
}
}
return false;
}
};
class Solution {
public:
bool oneEditAway(string first, string second) {
int len1 = first.length();
int len2 = second.length();
if(len1<len2){
// 调整 使得第一个字符串的长度大于第二个字符串的长度
return oneEditAway(second,first);
}
if(len1-len2>1){
return false;
}
// 这样的情况下 字符串长度要么相等 要么相差1
for(int i = 0;i<len2;i++){
if(first[i]!=second[i]){
// 如果两个字符串长度相等 就判断 i+1到末尾的字符串等不等 如果len1>len2 那么长的就从i+1起 短的就从i起
return first.substr(i+1)==second.substr(len1==len2?i+1:i);
}
}
return true;
}
};
结语
??突然好想谈恋爱了，不知道咋回事QAQ
