Given a non-empty string s, you may delete at most one character.  Judge whether you can make it a palindrome.


Example 1:

Input: "aba"
Output: True



Example 2:

Input: "abca"
Output: True
Explanation: You could delete the character 'c'.



Note:

The string will only contain lowercase characters a-z.
The maximum length of the string is 50000.

Source: leetcode | Difficulty: EASY
Tags: String algorithms

Amortized analysis

Greedy algorithms

Starter code: class Solution:
    def validPalindrome(self, s: str) -> bool:
        

Solutions:
class Solution:

	def validPalindrome(self, s):
		if s == s[::-1]:
			return True
		r = s[::-1]
		for i in range(0, len(s)):
			if r[i] == s[i]:
				continue
			else:
				break
		r = r[:i] + r[i + 1:]
		if r == r[::-1]:
			return True
		s = s[:i] + s[i + 1:]
		return s == s[::-1]


class Solution:

	def validPalindrome(self, s):
		if s == s[::-1]:
			return True
		for i in range(int(len(s) / 2)):
			if s[i] != s[-1 - i]:
				s1 = s[:i] + s[i + 1:]
				if s1 == s1[::-1]:
					return True
				s2 = s[:-1 - i] + s[len(s) - i:]
				if s2 == s2[::-1]:
					return True
				return False


class Solution:

	def validPalindrome(self, s):
		if s == s[::-1]:
			return True
		(i, j) = (0, len(s) - 1)
		while i < j:
			if s[i] == s[j]:
				i += 1
				j -= 1
			else:
				remove_i = s[:i] + s[i + 1:]
				remove_j = s[:j] + s[j + 1:]
				return remove_i == remove_i[::-1] or remove_j == remove_j[::-1]


class Solution:

	def validPalindrome(self, s):
		if s == s[::-1]:
			return True
		(i, j) = (0, len(s) - 1)
		dele = 1
		while i < j:
			if s[i] == s[j]:
				(i, j) = (i + 1, j - 1)
			else:
				(t1, t2) = (s[i + 1:j + 1], s[i:j])
				return t1 == t1[::-1] or t2 == t2[::-1]
		return True