Leetcode | Valid Palindrome II

Description:

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

Example:

Input: “aba”
Output: True

Input: “abca”
Output: True
Explanation: You could delete the character ‘c’.

Ideas:

In this case, chars have different situations, like''abc',"cbbcc"... as we can del one char, it means we need to del one while different char appear in matching low and high pointers. Then, its easy to judge whether the rest of chars is palindrome or not.
However, I just treated del char as a condition and used lost of conditionl statements. Its definitely not efficient.

Code:

class Solution(object):
    def validPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        def Judge_palindrome(low, high):
            while low < high:
                if s[low] == s[high]:
                    low += 1
                    high -= 1
                else:
                    return False
            return True

        i = 0
        j = len(s) - 1
        while i < j:
            if s[i] != s[j]:
                return Judge_palindrome(i+1, j) or Judge_palindrome(i, j-1)
            i += 1
            j -= 1

        return True

Execution time：128 ms
Memory consumption：13.8 MB

class Solution(object):
    def validPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        isPalindrome = lambda x : x == x[::-1]
        left, right = 0, len(s) - 1
        while left <= right:
            if s[left] == s[right]:
                left += 1
                right -= 1
            else:
                return isPalindrome(s[left + 1 : right + 1]) or isPalindrome(s[left: right])
        return True

作者：fuxuemingzhu
链接：https://leetcode-cn.com/problems/valid-palindrome-ii/solution/cong-liang-ce-xiang-zhong-jian-zhao-dao-bu-deng-de/
来源：力扣（LeetCode）

Execution time：72 ms
Memery consumption：13.8 MB

summary

We all know using a pair of pointers to traverse chars is necessary, one from head and one from tail, but process rest of the chars is key.