LeetCode 680 Valid Palindrome II

LeetCode

Given a string s, return true if the s can be palindrome after deleting at 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<sup>5</sup> s consists of lowercase English letters.

题目大意：

删除一个字符变成回文字符串

解题思路：

暴力法是O(n^2)，要优化到O(n)且这是关于元素之间的关系，考虑用Two pointers

解题步骤：

N/A

注意事项：

1. 当发现不相等的字符，不能简单认为s[i + 1] == s[j]就觉得应该删除左边字符，因为可能是刚好相等，如bddbd，第一个b和倒数第二个b相等，如果删除第一个b，就会得到False，所以应该删除左边字符和删除右边字符同时都要试

Python代码：

def validPalindrome(self, s: str) -> bool:
	i, j = 0, len(s) - 1
	while i < j:
		if s[i] != s[j]:
			if self.is_palindrome(s[i + 1:j + 1]) or self.is_palindrome(s[i:j]):
				return True
			else:
				return False
		i += 1
		j -= 1
	return True
	
def is_palindrome(self, s):
	return s == s[::-1]

算法分析：

时间复杂度为O(n)，空间复杂度O(1)