文章

[LeetCode] 每日一题 680. 验证回文串 II

题目链接

https://leetcode.cn/problems/valid-palindrome-ii

题目描述

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

请你判断 s 是否能成为回文字符串:如果能,返回 true ;否则,返回 false

示例输入

示例 1

输入:s = "aba"
输出:true

示例 2

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

示例 3

输入:s = "abc"
输出:false

提示

  • 1 <= s.length <= 10^5

  • s 由小写英文字母组成

解题思路

本题的目标是判断一个字符串是否能通过删除最多一个字符变成回文字符串。为了实现这一点,我们可以借助分治思想来判断

关键思路:

  1. 回文判断:我们从字符串两端开始向中间推进,逐一比较字符。如果字符相同,则继续向内比较。如果出现不同的字符,考虑两种情况:

    • 删除左边的字符并继续判断剩余部分是否为回文

    • 删除右边的字符并继续判断剩余部分是否为回文

  2. 如果以上两种情况中有一个能变成回文字符串,那么返回 true;否则,返回 false

通过递归调用,我们可以处理删除字符后的字符串,最终判断是否能形成回文字符串

代码实现

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

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

复杂度分析

  • 时间复杂度:O(n),其中 n 是字符串 s 的长度。最坏情况下我们需要两次遍历字符串(一次正常的遍历和一次删除字符后的遍历),因此时间复杂度是 O(n)

  • 空间复杂度:O(n),递归的深度最多是字符串的长度,所以空间复杂度是 O(n)

总结

本题利用分治思想,通过递归判断删除一个字符后的两种可能性,简洁地解决了问题。对于每次字符不匹配的情况,我们通过递归尝试删除左边或右边的字符,从而判断字符串是否能通过删除一个字符变成回文。该方法不仅能解决问题,而且效率较高,适合处理类似的回文判断问题。

希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。

License:  CC BY 4.0