LeetCode LCR 019. 验证回文串 II

Categories:

题目描述
思路分析
1. 解法一：双指针 + 一次容错（推荐）
相似题目

题目描述

✅ LCR 019. 验证回文串 II

思路分析

解法一：双指针 + 一次容错（推荐）

核心思路：

使用双指针从两端向中间移动。

第一次出现不匹配时，尝试跳过左边或右边一个字符继续判断。

只允许删除一次字符，因此只需检查两种情况。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(1)。

// 双指针容错判断
class Solution {
    public boolean validPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;

        while (left < right) {
            if (s.charAt(left) == s.charAt(right)) {
                left++;
                right--;
            } else {
                return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
            }
        }
        return true;
    }

    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

// 双指针容错判断
func validPalindrome(s string) bool {
	left, right := 0, len(s)-1
	for left < right {
		if s[left] == s[right] {
			left++
			right--
		} else {
			return isPalindrome(s, left+1, right) || isPalindrome(s, left, right-1)
		}
	}
	return true
}

func isPalindrome(s string, left, right int) bool {
	for left < right {
		if s[left] != s[right] {
			return false
		}
		left++
		right--
	}
	return true
}

相似题目

题目	难度	考察点
125. 验证回文串	简单	双指针
131. 分割回文串	中等	回溯
132. 分割回文串 II	困难	DP
214. 最短回文串	困难	字符串
647. 回文子串	中等	双指针

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/16187143