侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【双指针】一次编辑

GabrielxD
2022-05-14 / 0 评论 / 0 点赞 / 33 阅读 / 467 字 / 正在检测是否收录...

题目

面试题 01.05. 一次编辑


字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串,编写一个函数判定它们是否只需要一次(或者零次)编辑。

示例 1:

输入: 
first = "pale"
second = "ple"
输出: True

示例 2:

输入: 
first = "pales"
second = "pal"
输出: False

解题

方法一:双指针

思路

先对比两个字符串的长度,如果长度差大于 2 直接判否,返回 false

确保 first 的长度比 second 短(后面会用到),否则交换。

使用两个指针(fstIdx, secIdx)同时从 0 开始扫描两个字符串,并维护一个 editCnt 用于记录修改次数:

  • 如果两个指针指向的字符相同,两指针后移,直接进行下一次遍历
  • 两字符不相同时,必会发生修改,故先把修改次数加一,如果修改次数超过一直接返回 false
    • 如果两字符串长度相等,说明只能替换一个字符,两指针后移
    • 如果两字符串长度不等,说明要删除一个字符,因为前面保证了 first 的长度必比 second 短,则fstIdx 不动,secIdx 后移即代表删除了一个 second 中的字符

如果遍历完成,则 first 一定可以在经过一次以内的编辑变为 second,返回 true

代码

class Solution {
    public boolean oneEditAway(String first, String second) {
        int fstLen = first.length(), secLen = second.length();
        if (Math.abs(first.length() - second.length()) > 1) return false;
        if (fstLen > secLen) return oneEditAway(second, first);
        int editCnt = 0;
        for (int fstIdx = 0, secIdx = 0; fstIdx < fstLen && secIdx < secLen;) {
            char fstChar = first.charAt(fstIdx), secChar = second.charAt(secIdx);
            if (fstChar == secChar) {
                fstIdx++;
                secIdx++;
            } else {
                if (++editCnt > 1) return false;
                if (fstLen == secLen) {
                    fstIdx++;
                    secIdx++;
                } else secIdx++;
            }
        }
        return true;
    }
}
0

评论区