LeetCode 680 Valid Palindrome II

LeetCode

<div>

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

Example 1:

<pre>Input: s = "aba" Output: true </pre>

Example 2:

<pre>Input: s = "abca" Output: true Explanation: You could delete the character 'c'. </pre>

Example 3:

<pre>Input: s = "abc" Output: false </pre>

Constraints:

1 <= s.length <= 10<sup>5</sup>
s consists of lowercase English letters.

</div>

题目大意：

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

解题思路：

暴力法是O(n^2)，要优化到O(n)且这是关于元素之间的关系，考虑用Two pointers。这题更类似于DP，假设左部分和右部分已经是回文，现在比较a[i]和a[j]，两种可能，这是只有一步的DP。

解题步骤：

N/A

注意事项：

当发现不相等的字符，不能简单认为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)