[LeetCode]Valid Palindrome II

题目描述:

LeetCode 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:

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

题目大意:

给定一个非空字符串s,至多删除一个字符。判断是否可以组成回文。

解题思路:

双指针(Two Pointers)

lo, hi分别指向s的左右两侧,向中心移动

当s[lo] != s[hi]时,判断删掉lo或者hi时,剩余字符串是否为回文

Python代码:

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

 

本文链接:http://bookshadow.com/weblog/2017/09/17/leetcode-valid-palindrome-ii/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码