【重来】【vip】5. Longest Palindromic Substring【m】【30】【97】

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

So, it becomes simple, you only need to scan from beginning to the end, adding one character at a time, keeping track of maxPalindromeLen, and for each added character, you check if the substrings ending with this new character, with length P+1 or P+2, are palindromes, and update accordingly.

Now, this is O(n^2) as taking substrings and checking palindromicity seem O(n) time. We can speed up it by realizing that strings are immutable, and there are memory slicing tricks will help to speed these operations up. comparing string equality with "==" is O(1), and using slicing to substring and reverse is ̶a̶l̶s̶o̶ ̶O̶(̶1̶)̶ ̶(̶n̶o̶t̶ ̶t̶o̶t̶a̶l̶l̶y̶ ̶s̶u̶r̶e̶ ̶a̶b̶o̶u̶t̶ ̶t̶h̶e̶ ̶s̶l̶i̶c̶i̶n̶g̶ ̶t̶h̶o̶u̶g̶h̶.̶ ̶ ̶I̶ ̶t̶h̶i̶n̶k̶ ̶i̶t̶ ̶i̶s̶ ̶O̶(̶1̶)̶,̶ ̶b̶u̶t̶ ̶c̶o̶u̶l̶d̶ ̶n̶o̶t̶ ̶f̶i̶n̶d̶ ̶a̶n̶y̶ ̶s̶o̶l̶i̶d̶ ̶l̶i̶t̶e̶r̶a̶t̶u̶r̶e̶ ̶a̶b̶o̶u̶t̶ ̶i̶t̶.̶ O(n) (thanks to ChuntaoLu). But as slicing is optimized by the interpreter's C code, it should run pretty fast. I'm pretty new to Python. Would appreciate you would give more insights or further optimization.

class Solution(object):def longestPalindrome(self, s):if len(s)==0:return 0maxLen=1start=0for i in xrange(len(s)):print i,s[i],s[start:start+maxLen]if i-maxLen >=1 and s[i-maxLen-1:i+1]==s[i-maxLen-1:i+1][::-1]:print s[i-maxLen-1:i+1]start=i-maxLen-1maxLen+=2continueif i-maxLen >=0 and s[i-maxLen:i+1]==s[i-maxLen:i+1][::-1]:start=i-maxLenmaxLen+=1return s[start:start+maxLen]'''这是n^2的解法def helper(s,l,r):while l>= 0 and r< len(s) and s[l] == s[r]:l-=1r+=1return s[l+1:r]maxx = 0res = ''for i in xrange(len(s)):tmp = helper(s,i,i)if len(tmp) > len(res):res = tmptmp = helper(s,i,i+1)if len(tmp) > len(res):res = tmpreturn res''''''for i in xrange(len(s)):for j in xrange(len(s)-i -1,maxx,-1):#print i,j,s[i:i+j]#print i,jif s[i] != s[i+j]:continuepos = 0while pos <= j/2 and s[i+pos] == s[i+j-pos]:pos += 1if pos == j/2 + 1 and maxx < j:res = s[i:i+j+1]maxx = jt = s[i:i+j]tt = t[::-1]if t == tt:if j > maxx:res = tmaxx = max(maxx,j)return res'''""":type s: str:rtype: str"""