680. 验证回文串 II

🟢   🔖  贪心 双指针 字符串  🔗 力扣 LeetCode

题目

Given a string s, return true if thes can be palindrome after deletingat most one character from it.

Example 1:

Input: s = "aba"

Output: true

Example 2:

Input: s = "abca"

Output: true

Explanation: You could delete the character 'c'.

Example 3:

Input: s = "abc"

Output: false

Constraints:

• 1 <= s.length <= 10^5
• s consists of lowercase English letters.

题目大意

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

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

示例 1：

输入： s = "aba"

输出： true

示例 2：

输入： s = "abca"

输出： true

解释： 你可以删除字符 'c' 。

示例 3：

输入： s = "abc"

输出： false

提示：

• 1 <= s.length <= 10^5
• s 由小写英文字母组成

解题思路

1. 判断回文：

   • 一个字符串 s 是回文，当且仅当 s[i] == s[s.length - 1 - i]，对于所有的 i，满足这个条件。
   • 定义辅助函数 isPalindrome，用于判断子字符串是否为回文字符串，使用双指针从两端向中间推进。

2. 具体步骤：

   • 使用双指针 left 和 right 从字符串两端向中间进行遍历。
   • 如果 s[left] === s[right]，则继续向中间推进，检查下一个字符。
   • 如果 s[left] !== s[right]，我们有两种选择：
     1. 删除 left 指针指向的字符，检查从 left + 1 到 right 的子字符串是否为回文。
     2. 删除 right 指针指向的字符，检查从 left 到 right - 1 的子字符串是否为回文。
   • 如果两种删除方式中有一种能让字符串成为回文，则返回 true；否则返回 false。

3. 边界条件：

   • 如果字符串本身已经是回文，直接返回 true。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串 s 的长度。最坏情况下，最多需要两次遍历整个字符串。
• 空间复杂度：O(1)，只使用了常数空间来进行计算。

代码

/**
 * @param {string} s
 * @return {boolean}
 */
var validPalindrome = function (s) {
	// 判断字符串是否是回文
	const isPalindrome = (str, left, right) => {
		while (left < right) {
			if (str[left++] !== str[right--]) return false;
		}
		return true;
	};

	let left = 0,
		right = s.length - 1;

	// 双指针检查是否是回文
	while (left < right) {
		if (s[left] === s[right]) {
			left++;
			right--;
		} else {
			// 尝试删除一个字符，检查两种情况
			return (
				isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1)
			);
		}
	}

	// 如果经过上述检查后仍然是回文
	return true;
};

相关题目

题号	标题	题解	标签	难度	力扣
125	验证回文串	[✓]	双指针 字符串	🟢	🀄️ 🔗
1216	验证回文串 III 🔒		字符串 动态规划	🔴	🀄️ 🔗
2330	验证回文串 IV 🔒		双指针 字符串	🟠	🀄️ 🔗