【LeetCode】5. Longest Palindromic Substring

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

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

题意：求最长回文串。

思路：我是从discuss区看到的，整体思路事从用两个指针j,k从内往外遍历，当遇到不能使回文成立的条件时，更新最大值记录

 1 class Solution(object):
 2     def longestPalindrome(self, s):
 3         """
 4         :type s: str
 5         :rtype: str
 6         """
 7         if len(s)==0: return ''
 8         if len(s)==1: return s
 9         front = 0
10         l = 0
11         for i in range(len(s)):
12             if len(s)-i<l/2: break #当后面的字符串已经不能更新最大值时
13             j = k = i
14             while k+1<len(s) and s[k] == s[k+1]: k += 1 #跳过一样的字符
15             while j>0 and k+1<len(s) and s[j-1] == s[k+1]:  #从里往外遍历
16                 j -= 1
17                 k += 1
18             if k-j+1 > l:
19                 front = j
20                 l = k-j+1
21         return s[front:front+l]