Valid Palindrome II

云计算 waitig 539℃ 百度已收录 0评论

题目链接:https://leetcode.com/problems/valid-palindrome-ii/description/
做这道题真是“路途艰辛”啊。一开始我就想到会不会有什么套路,想了半天没有想出来。后来干脆先暴力,果然有时间限制。然后自然而然的想到要降低时间复杂度,只检查字符不同的位置就行了,结果还是超时[衰]。再后来就开始认认真真的分析这道题的“套路”了。
因为只能删除一个元素,删除该元素后,字符串变为一个回文串。让我们来看一个例子 s=”abcde”,rs表示s的倒置。来发现解题的思路,为了便于发现思路,再括号之外的为删除的元素。
1、假定删除s中第一个元素后,s=”bcde”,rs=”edcb”
s= a (b c d e)
rs= (e d c b) a
2、假定删除s中第二个元素后,s=”acde”,rs=”edca”
s=(a) b (c d e)
rs=(e d c) b (a)
3、假定删除s中的第三个元素后,s=”abde”.rs=”edba”
s=(a b) c (d e)
rs=(e d) c (b a)
4、假定删除s中的第4个元素后,s=”abce”,rs=”ecba”
s=(a b c) d (e)
rs=(e) d (c b a)
5、假定删除s中的第4个元素后,s=”abcd”,rs=”dcba”
s=(a b c d) e
rs=e (d c b a)
删除第一个元素后,好像没什么启示;删除第二个元素后,因为第一个元素(s的第一个元素为a,rs的第一个元素为e)不等,所以删除第二个元素后,不会使s成为回文串;删除第三个元素后,同理因为s的第一个元素和rs的最后一个元素不等,也不会使s成为一个回文串;同理可得…….

通过以上发现,如果删除某个位置index的字符后字符串成为回文串,那么index左边的元素和length-index-1右边的元素倒序之后必须是相等的,才能删除某个位置index上的字符后成为回文串。

我通过以上启示思路,找到s中第一个不等的位置,假定位置为index,那么该位置对应的s的后边的元素位置为length-index-1,尝试删除index位置上元素和length-index-1上的元素,如果能构成回文串的话,返回True;不能构成的话,以后也肯定构不成回文串了。

不清楚我解释的够不够明确,情不清晰?

后来感觉其实这题也不难,就是需要找到其中的规律而已,关键有时候找不到啊[哭]


正确解法如下:

class Solution(object):
    def validPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if s==s[::-1]:
            return True
        #执行到这,说明肯定有前后不等的字符,一定会执行到else语句
        length,count=len(s),0
        i,j=0,length-1
        while i<j:
            if s[i]==s[j]:
                i,j=i+1,j-1
            else:
                return s[i+1:j+1]==s[i+1:j+1][::-1] or s[i:j]==s[i:j][::-1]#s[i]!=s[j],即找到第一个不相等字符的位置

暴力解法,超时了

# -*- coding:utf-8 -*-
class Solution(object):
    def validPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        reverse=s[::-1]#取得s的逆序字符串,s='abc',reversedS='cba'
        if reverse==s:
            return True
        length=len(s)#s的长度
        for i in range(length):#执行到这,说明需要删除一个元素,以构成回文
            temp=s[0:i]+s[i+1:]#构造新的字符串
            reverseTemp=reverse[0:length-i-1]+reverse[length-i:]#
            # print temp,reverseTemp
            if temp==reverseTemp:
                return True
        return False

改进版的暴力,还是超时:

class Solution(object):
    def validPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        reverse=s[::-1]#取得s的逆序字符串,s='abc',reversedS='cba'
        if reverse==s:
            return True
        length=len(s)#s的长度
        check=[]#需要检查的位置
        for i in range(length/2):
            if s[i]!=s[length-i-1]:
                check.append(i)
                check.append(length-i-1)
        #print check
        for i in check:#执行到这,说明需要删除一个元素,以构成回文
            temp=s[0:i]+s[i+1:]#构造新的字符串
            reverseTemp=reverse[0:length-i-1]+reverse[length-i:]#
            # print temp,reverseTemp
            if temp==reverseTemp:
                return True
        return False

本文由【waitig】发表在等英博客
本文固定链接:Valid Palindrome II
欢迎关注本站官方公众号,每日都有干货分享!
等英博客官方公众号
点赞 (0)分享 (0)