LeetCode 680: Valid Palindrome II (Two-Pointer One-Deletion Check)
LeetCode 680Two PointersStringInterviewToday we solve LeetCode 680 - Valid Palindrome II.
Source: https://leetcode.com/problems/valid-palindrome-ii/
English
Problem Summary
Given a string s, return true if it can become a palindrome after deleting at most one character. Otherwise return false.
Key Insight
Use two pointers from both ends. As long as characters match, move inward. At the first mismatch, we only get one deletion chance, so we must check either skipping left (i+1..j) or skipping right (i..j-1).
Brute Force and Limitations
Brute force tries deleting each index and checks palindrome each time: O(n^2). This is unnecessary because only the first mismatch matters in the optimal two-pointer flow.
Optimal Algorithm Steps
1) Set i=0, j=n-1.
2) While i<j, if s[i]==s[j], move both pointers.
3) On first mismatch, return isPal(i+1,j) || isPal(i,j-1).
4) If no mismatch appears, return true.
Complexity Analysis
Time: O(n), because helper palindrome checks are linear and triggered once.
Space: O(1).
Common Pitfalls
- Continuing to allow more than one deletion after mismatch.
- Writing helper boundaries incorrectly (l/r inclusive).
- Forgetting that an already-palindrome string should return true.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public boolean validPalindrome(String s) {
int i = 0, j = s.length() - 1;
while (i < j) {
if (s.charAt(i) == s.charAt(j)) {
i++;
j--;
} else {
return isPal(s, i + 1, j) || isPal(s, i, j - 1);
}
}
return true;
}
private boolean isPal(String s, int l, int r) {
while (l < r) {
if (s.charAt(l++) != s.charAt(r--)) return false;
}
return true;
}
}func validPalindrome(s string) bool {
i, j := 0, len(s)-1
for i < j {
if s[i] == s[j] {
i++
j--
} else {
return isPal(s, i+1, j) || isPal(s, i, j-1)
}
}
return true
}
func isPal(s string, l, r int) bool {
for l < r {
if s[l] != s[r] {
return false
}
l++
r--
}
return true
}class Solution {
public:
bool validPalindrome(string s) {
int i = 0, j = (int)s.size() - 1;
while (i < j) {
if (s[i] == s[j]) {
++i;
--j;
} else {
return isPal(s, i + 1, j) || isPal(s, i, j - 1);
}
}
return true;
}
bool isPal(const string& s, int l, int r) {
while (l < r) {
if (s[l++] != s[r--]) return false;
}
return true;
}
};class Solution:
def validPalindrome(self, s: str) -> bool:
def is_pal(l: int, r: int) -> bool:
while l < r:
if s[l] != s[r]:
return False
l += 1
r -= 1
return True
i, j = 0, len(s) - 1
while i < j:
if s[i] == s[j]:
i += 1
j -= 1
else:
return is_pal(i + 1, j) or is_pal(i, j - 1)
return Truevar validPalindrome = function(s) {
let i = 0, j = s.length - 1;
const isPal = (l, r) => {
while (l < r) {
if (s[l] !== s[r]) return false;
l++;
r--;
}
return true;
};
while (i < j) {
if (s[i] === s[j]) {
i++;
j--;
} else {
return isPal(i + 1, j) || isPal(i, j - 1);
}
}
return true;
};中文
题目概述
给定字符串 s，你最多可以删除一个字符。若能变成回文串，返回 true；否则返回 false。
核心思路
双指针从两端向中间收缩。遇到第一处不相等时，只有一次删除机会，因此只需尝试两种情况：删左字符（检查 i+1..j）或删右字符（检查 i..j-1）。任一成立即可。
暴力解法与不足
暴力做法是枚举每个删除位置并重新判断是否回文，复杂度为 O(n^2)。而双指针只在第一次冲突处分叉一次，能降到线性时间。
最优算法步骤
1）初始化 i=0、j=n-1。
2）若 s[i]==s[j]，双指针继续内缩。
3）若不相等，返回 isPal(i+1,j) || isPal(i,j-1)。
4）若遍历完都没冲突，说明原串已是回文，返回 true。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1)。
常见陷阱
- 不相等后继续“多次删除”，违反题意。
- 辅助回文函数边界写错（左右端点是闭区间）。
- 忘记原串本身就是回文时应返回 true。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public boolean validPalindrome(String s) {
int i = 0, j = s.length() - 1;
while (i < j) {
if (s.charAt(i) == s.charAt(j)) {
i++;
j--;
} else {
return isPal(s, i + 1, j) || isPal(s, i, j - 1);
}
}
return true;
}
private boolean isPal(String s, int l, int r) {
while (l < r) {
if (s.charAt(l++) != s.charAt(r--)) return false;
}
return true;
}
}func validPalindrome(s string) bool {
i, j := 0, len(s)-1
for i < j {
if s[i] == s[j] {
i++
j--
} else {
return isPal(s, i+1, j) || isPal(s, i, j-1)
}
}
return true
}
func isPal(s string, l, r int) bool {
for l < r {
if s[l] != s[r] {
return false
}
l++
r--
}
return true
}class Solution {
public:
bool validPalindrome(string s) {
int i = 0, j = (int)s.size() - 1;
while (i < j) {
if (s[i] == s[j]) {
++i;
--j;
} else {
return isPal(s, i + 1, j) || isPal(s, i, j - 1);
}
}
return true;
}
bool isPal(const string& s, int l, int r) {
while (l < r) {
if (s[l++] != s[r--]) return false;
}
return true;
}
};class Solution:
def validPalindrome(self, s: str) -> bool:
def is_pal(l: int, r: int) -> bool:
while l < r:
if s[l] != s[r]:
return False
l += 1
r -= 1
return True
i, j = 0, len(s) - 1
while i < j:
if s[i] == s[j]:
i += 1
j -= 1
else:
return is_pal(i + 1, j) or is_pal(i, j - 1)
return Truevar validPalindrome = function(s) {
let i = 0, j = s.length - 1;
const isPal = (l, r) => {
while (l < r) {
if (s[l] !== s[r]) return false;
l++;
r--;
}
return true;
};
while (i < j) {
if (s[i] === s[j]) {
i++;
j--;
} else {
return isPal(i + 1, j) || isPal(i, j - 1);
}
}
return true;
};
Comments