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天倒计时,蓝桥杯省赛备赛攻略来啦~