LeetCode 面试题 01.05. 一次编辑 (字符串 / 双指针)
思路
- 首先判断两个字符串长度,因为只能编辑一次,所以两字符串的差值只能在 -1 0 1 这三个之中;
- 得到差值之后,定义与两个字符串对应的双指针Findex、Sindex和变化次数count,进入字符串遍历的循环当中;
- 如果first长度大于second(或者second长度大于first),则发现两字符某字符不同时,对应的Findex、Sindex增加(插入、删除的逻辑,一次改变),count++;然后下一次循环
- 如果长度相等,则字符不同时,就进行替换逻辑,count++;
- 过程中如果发现count > 1,则说明不止一次编辑,返回false;否则循环结束就返回true。
代码实现(java)
class Solution {
public boolean oneEditAway(String first, String second) {
int len =first.length() - second.length();
if(len > 1 || len < -1) {
return false;
}
if(first == null && second == null) return true;
if(first.equals(second)) return true;
int Findex = 0;
int Sindex = 0;
int count = 0; // 变换的次数
while(Findex < first.length() && Sindex < second.length()) {
if(len == 1) {
// first长度大于second,发现字符不同,first删除(或者是second插入)对应着Findex++,count++
if(first.charAt(Findex) != second.charAt(Sindex)) {
Findex++;
count++;
} else {
Findex++;
Sindex++;
}
} else if(len == -1) {
// second长度大于first,发现字符不同,second删除(或者是first插入)对应着Sindex++,count++
if(first.charAt(Findex) != second.charAt(Sindex)) {
Sindex++;
count++;
} else {
Findex++;
Sindex++;
}
} else if(len == 0) {
// 两字符串长度相同,发现不同字符则进行替换,count++
if(first.charAt(Findex) != second.charAt(Sindex)) {
count++;
}
Findex++;
Sindex++;
}
// 每次循环都判断count是否大于1(编辑次数大于一次),如果大于1,则返回false
if(count > 1) return false;
}
// 循环结束,编辑次数不大于1,则返回false
return true;
}
}
上一篇:
92天倒计时,蓝桥杯省赛备赛攻略来啦~
