680. Valid Palindrome II

Given a non-empty strings, you may deleteat mostone 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:

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

Thoughts:

1. Try to compare the head and tail char, if not equal then try compare (head + 1, tail) and (head, tail- 1).

class Solution(object):
    def validPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        def isPalindrome(s, start, end):
            while start < end:
                if s[start] != s[end]: return False
                start += 1
                end -= 1
            return True

        start, end = 0, len(s) - 1

        while start < end:
            if s[start] != s[end]: return isPalindrome(s, start + 1, end) or isPalindrome(s, start, end -1)
            start+=1
            end-=1

        return True