专栏首页WD学习记录LeetCode Longest Palindromic Substring

LeetCode 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 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

解法1:参考 [LeetCode]题解(python):005-Longest Palindromic Substring

class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        n=len(s)
        if n==1 or n==0:
            return s
        if n==2:
            if s[0]==s[1]:
                return s
            else:
                return s[0]
        max_length=1
        ans=s[0]
        i=0
        while i<n:
            j=i+1
            while j<n:
                if s[i]==s[j]:
                    j+=1
                else:
                    break
            k=0
            while i-k-1>=0 and j+k<=n-1:
                if s[i-k-1]!=s[j+k]:
                    break
                k+=1
            if j-i+2*k>max_length:
                max_length=j-i+2*k
                ans=s[i-k:j+k]
            # if j+k==n-1:
            #    break
            i=j
        return ans

解法2:参考sample 52 ms submission

class Solution:
    def longestPalindrome(self, s):
        if s == s[::-1]:
            return s
        Len, start  = 1, 0
        for i in range(1, len(s)):
            c, d = i - Len, i + 1
            if c >= 1:
                x = s[c - 1:d]
                if x == x[::-1]:
                    start = c - 1
                    Len += 2
                    continue
            if c >= 0:
                x = s[c:d]
                if x == x[::-1]:
                    start = c
                    Len += 1
        return s[start:start + Len]

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java8 hashmap

    HashMap是java集合类中一种常见的集合类型,在面试中多次被问到。这里根据面试中的问题稍微整理一下。

  • 牛客网 旋转数组的最小值

    把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为...

  • 数值的整数次方

  • R条件语句

    但如果你有一长串 if 语句,那么就要考虑重写了。重写的一种方法是使用 switch() 函数, 它先对第一个参数求值,然后按照名称或位置在后面的参数列表中匹...

    生信编程日常
  • R语言写2048游戏

           2048 是一款益智游戏,只需要用方向键让两两相同的数字碰撞就会诞生一个翻倍的数字,初始数字由 2 或者 4 构成,直到游戏界面全部被填满,游戏结...

    用户1680321
  • 【趣解编程】条件语句if

    遇见if,就是走到了分岔路口,需要根据当前拥有的条件和环境,来决断到底要走哪一条路。

    一斤代码
  • 一道简单但易错的C语言面试题

    正确答案是B选项。首先,要注意的一点是这里的if判断条件里用的是=号,而不是==号,这个小陷阱可能会迷惑一些初学C语言的朋友。如果这里用的是==号的话,正确答案...

    正念君
  • js中判断对象是否为空的三种实现方法

    在写js脚本的时候经常遇到对象为空或者不是对象的情况,出现这种情况我们可以用if去判断它,然后去执行相应的处理方法,具体判断他们的方法有以下几种:

    跟着阿笨一起玩NET
  • 终于让采集侠自动采集了

    用织梦采集侠一段时间了,觉得这个插件真的不错,尤其是新版本,可以结合DEDE自动的采集规则来进行采集。一下采集功能就非常强大了。

    用户1191760
  • python条件执行

    mwangblog

扫码关注云+社区

领取腾讯云代金券