5. Longest Palindromic Substring

  1. Longest Palindromic Substring
  2. 思路:

Longest Palindromic Substring

Medium
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"

思路:

  1. 循环遍历每一个字符
  2. 以每一个字符为中心向两边+1判断是否是回文字符串
  3. 区分奇偶的两种情况(具体见上面两个例子)
class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        res = ""
        for i in range(len(s)):
            tmp=self.helper(s,i,i)
            if len(tmp)>=len(res):
                res=tmp
            tmp=self.helper(s,i,i+1)
            if len(tmp)>=len(res):
                res=tmp
        return res

    def 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]

请多多指教。

文章标题:5. Longest Palindromic Substring

本文作者:顺强

发布时间:2019-11-23, 23:59:00

原始链接:http://shunqiang.ml/leetcode-5-longest-palindromic-substring/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏