【LeetCode】680.验证回文串 II

Bummon2023-08-22

680. 验证回文串 II

题目

给你一个字符串 s，最多可以从中删除一个字符。

请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。

示例 1：

1 2	输入： s = "aba" 输出： true

示例 2：

1
2
3

输入： s = "abca"
输出： true
解释： 你可以删除字符 'c' 。

示例 3：

1 2	输入： s = "abc" 输出： false

提示：

1 <= s.length <= 105
s 由小写英文字母组成

双指针法

思路分析

在使用 双指针法 的时候，我们可以定义一个开始下班 start 和一个结束下标 end ，start 由头至尾遍历，end 由尾至头遍历，当 start > end 时结束遍历。

通过题目中描述我们可以知道：一个字符串至多删除一个字符。那么我们遇到 start 下标的字符与 end 下标的字符不匹配的时候，我们尝试删除 start 右边的元素，并和 end 下标的元素是否匹配，若匹配则继续对比其他元素，或者我们尝试删除 end 左边的元素，并和 start 下标的元素是否匹配，同样的，如果匹配则继续对比其他元素，如下：

当 start 下标的元素与 end 下标的元素相同时，继续遍历比对。
当 start 下标的元素与 end 下标的元素不同时：
- 当 start + 1 下标的元素与 end 下标的元素匹配时，继续遍历比对。
- 当 end - 1 下标的元素与 start 下标的元素匹配时，继续遍历比对。
- 当 start + 1 下标的元素与 end 下标的元素不匹配，且 end - 1 下标的元素与 start 下标的元素均不匹配时，则该字符串不是回文字符串。
当 start 元素与 end 元素均两两相同时，则该字符串为回文字符串。

图解

未命名文件.gif

代码实现

public boolean validPalindrome(String s) {
        for (int start = 0, end = s.length() - 1; start < end; start++, end--) {
            if (s.charAt(start) != s.charAt(end)) {
                return isPalidrome(s, start, end - 1) || isPalidrome(s, start + 1, end);
            }
        }
        return true;
    }

    private boolean isPalidrome(String s, int start, int end) {
        while (start < end) {
            if (s.charAt(start++) != s.charAt(end--)) {
                return false;
            }
        }
        return true;
    }