680.md

680. Valid Palindrome II

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.

my thoughts:

1. regular two pointer check till the first exception occurs, check the [1:] and [:l-1] if either is palindrome.

my solution:

**********235ms
class Solution(object):
    def validPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        l = len(s)
        if l<2:
            return True
        p1 = 0
        p2 = l-1
        while p1<p2:
            if s[p1] == s[p2]:
                p1 += 1
                p2 -= 1
            else:
                break
        if p1>=p2:
            return True
        pa1 = p1+1
        pa2 = p2
        while pa1<pa2:
            if s[pa1] == s[pa2]:
                pa1 += 1
                pa2 -= 1
            else:
                break
        if pa1>=pa2:
            return True
        
        pb1 = p1
        pb2 = p2-1
        while pb1<pb2:
            if s[pb1] == s[pb2]:
                pb1 += 1
                pb2 -= 1
            else:
                break
        if pb1>=pb2:
            return True
        
        return False

my comments:

from other ppl's solution:

1. compare string is faster than iterate and compare chars, 89ms:
class Solution(object):
    def validPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
#         i = 0
#         while i<len(s)/2 and s[i]==s[~i]: i+=1
#         s = s[i:len(s)-i]
#         return s[1:]==s[1:][::-1] or s[:-1] == s[:-1][::-1]
    
        rev = s[::-1]
        if s == rev: return True
        l = len(s)
        for i in xrange(l):
            if s[i] != rev[i]:
                return s[i:l-i-1] == rev[i+1:l-i] or rev[i:l-i-1] == s[i+1:l-i]
        return False