LeetCode Notes_#5 Longest Palindromic Substring

LeetCode

Contents

题目

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"

Output: "bb"

思路和解答

思路

有点像之前的#9 Palindrome Number,又有点像昨天写的#3 Longest Substring Without Repeating Characters

于是我的第一想法还是暴力循环...先写一个判断回文字符串的函数，然后用这个函数找出所有的回文字符串，找到最长的
- 从每个字符串开始的所有回文串

是否可以借鉴#3里边的写法呢？
- 用一个滑动窗口来遍历
  - 其实就是左右两个指针，需要如何控制才能保证不漏掉任何一种回文串？
    - 感觉对于回文串这种，不太好从前往后一遍就检查到...
    - 难点在于：例如abbaabba
    - 有一个想法：不是从每个字符后面开始遍历，而是从每个字符的两边开始遍历，以这个字符为中心，两边的指针不断扩大，直到得到以这个字符为中心的最大的回文串，如果比最长回文串还长，就成为新的最长回文串，否则就不管。这个还需要区分奇偶，有可能是以两个字符串为中心
  - 得到一个回文串之后，可左右同时扩展，然后检验是否是回文串
- 用字典存储关键信息
  - #3的重点在于判断是否有重复
  - 这题重点在于判断回文字符串，一旦发现就加入字典，然后以长度作为索引？
    - 这里不需要，因为我没有'查询'的需求，我只需要维护一个max变量，不断地更新，就不需要把所有找到的回文字符串都存下来
  - #9里边的对称规律是否能应用过来呢？
    - 可以用于判断回文数的函数

s='aba'reverse=''for k in range(len(s)):       reverse=reverse+s[len(s)-1-k]if reverse==s:    print (True)else:    print (False)

True

s[0:3]#如果要通过切片的方式访问到字符串s最后一个字符，那么上限应该是len(s)

'aba'

s[0:4]#如果上限超过len(s),返回结果也是截止到最后一个字符

'aba'

#错误尝试,超时了class Solution(object):    def longestPalindrome(self, s):        """        :type s: str        :rtype: str        """        if len(s)<=1:            return s        else:            maxPalindrome=''            for i in range(len(s)):                for j in range(i+1,len(s)+1):#range上限是len(s)+1,只能取到len(s)                    tmpString=s[i:j]                    if self.isPalindrome(tmpString) and len(tmpString)>len(maxPalindrome):                        maxPalindrome=tmpString            return maxPalindrome                                                def isPalindrome(self,tmpS):        reverse=''        for k in range(len(tmpS)):            reverse=reverse+tmpS[len(tmpS)-1-k]        if reverse==tmpS:            return True        else:            return False

type(min(1,2))

int

#再一次尝试，有些testcase通不过，感觉还是索引的问题，字符串的索引真的很麻烦那class Solution(object):    def longestPalindrome(self, s):        """        :type s: str        :rtype: str        """        if len(s)<=1:            return s        if len(s)==2 and s[0]!=s[1]:            return s[0]        elif len(s)==2 and s[0]==s[1]:            return s        else:            maxPalindrome=''            for i in range(0,len(s)-1):                maxHalfLen=int(min(i,len(s)-i-1))                tmpStringOdd=s[i-maxHalfLen:i+maxHalfLen]                tmpStringEven=s[i-maxHalfLen:i+maxHalfLen+1]                if self.isPalindrome(tmpStringOdd) and len(tmpStringOdd)>len(maxPalindrome):                    maxPalindrome=tmpStringOdd                if self.isPalindrome(tmpStringEven) and len(tmpStringEven)>len(maxPalindrome):                    maxPalindrome=tmpStringEven                if s[i]==s[i+1] and len(maxPalindrome)<2:                    maxPalindorme=s[i:i+2]                            return maxPalindrome                                    def isPalindrome(self,tmpS):        reverse=''        for k in range(len(tmpS)):            reverse=reverse+tmpS[len(tmpS)-1-k]        if reverse==tmpS:            return True        else:            return False

解答

def longestPalindrome(self, s):    res = ""    for i in xrange(len(s)):        # odd case, like "aba"        tmp = self.helper(s, i, i)        if len(tmp) > len(res):            res = tmp        # even case, like "abba"        tmp = self.helper(s, i, i+1)        if len(tmp) > len(res):            res = tmp    return res # get the longest palindrome, l, r are the middle indexes   # from inner to outerdef helper(self, s, l, r):    while l >= 0 and r < len(s) and s[l] == s[r]:        l -= 1; r += 1    return s[l+1:r]