Python3最长回文子串算法示例

本文实例讲述了Python3最长回文子串算法。分享给大家供大家参考，具体如下：

1. 暴力法

思路：对每一个子串判断是否回文

class Solution:
  def longestPalindrome(self, s):
    """
    :type s: str
    :rtype: str
    """
    if len(s) == 1:
      return s
    re = s[0]
    for i in range(0,len(s)-1):
      for j in range(i+1,len(s)):
        sta = i
        end = j
        flag = True
        while sta < end:
          if s[sta] != s[end]:
            flag = False
            break
          sta += 1
          end -= 1
        if flag and j-i+1 > len(re):
          re = s[i:j+1]
    return re

提交结果：超出时间限制

2. 动态规划法

思路：

m[i][j]标记从第i个字符到第j个字符构成的子串是否回文，若回文值为True，否则为False.

初始状态 s[i][i] == True，其余值为False.

当 s[i] == s[j]  and m[i+1][j-1] == True 时，m[i][j] = True

class Solution:
  def longestPalindrome(self, s):
    """
    :type s: str
    :rtype: str
    """
    k = len(s)
    matrix = [[False for i in range(k)] for j in range(k)]
    re = s[0:1]
    for i in range(k):
      for j in range(k):
        if i==j:
          matrix[i][j] = True
    for t in range(1,len(s)):       #分别考虑长度为2~len-1的子串（长串依赖短串的二维数组值）
      for i in range(k):
        j = i+t
        if j >= k:
          break
        if i+1 <= j-1 and matrix[i+1][j-1]==True and s[i] == s[j]:
          matrix[i][j] = True
          if t+1 > len(re):
            re = s[i:j+1]
        elif i+1 == j and j-1 == i and s[i] == s[j]:
          matrix[i][j] = True
          if t+1 > len(re):
            re = s[i:j+1]
    return re

执行用时：8612 ms

更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述对大家Python程序设计有所帮助。

赞 (0)

相关推荐

  • Python简单实现阿拉伯数字和罗马数字的互相转换功能示例

    Python简单实现阿拉伯数字和罗马数字的互相转换功能示例

    本文实例讲述了Python实现阿拉伯数字和罗马数字的互相转换功能.分享给大家供大家参考,具体如下: 前面一篇介绍了<Java实现的求解经典罗马数字和阿拉伯数字相互转换问题>,这里来看看Python的实现方法. 题目很简单,如果之前也做过这种题目的话,相信对于什么是罗马数字就不会很陌生了,罗马数字是很古老的计数方法,现在的一些地方还有见到它的使用,下面简单贴两张维基百科的图片简单回顾一下罗马数字: 今天简单实现一下,阿拉伯数字和罗马数字之间的相互转化问题,很简单就不多说了,下面是具体的实现: #

  • Python3实现的回文数判断及罗马数字转整数算法示例

    本文实例讲述了Python3实现的回文数判断及罗马数字转整数算法.分享给大家供大家参考,具体如下: 回文数 判断一个整数是否是回文数.回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数. 示例 1: 输入: 121 输出: true 示例 2: 输入: -121 输出: false 解释: 从左向右读, 为 -121 . 从右向左读, 为 121- .因此它不是一个回文数. 示例 3: 输入: 10 输出: false 解释: 从右向左读, 为 01 .因此它不是一个回文数. 进阶:你

  • Python实现判断一个整数是否为回文数算法示例

    Python实现判断一个整数是否为回文数算法示例

    本文实例讲述了Python实现判断一个整数是否为回文数算法.分享给大家供大家参考,具体如下: 第一个思路是先将整数转换为字符串,再将字符串翻转并与原字符串做比较 def isPalindrome(self, x): """ :type x: int :rtype: bool """ #思路:先将整数转换为字符串,再将字符串翻转并与原字符串做比较 x = str(x) return x == x[::-1] 代码简洁 第二个思路,尝试着不用字符串,

  • Python将阿拉伯数字转换为罗马数字的方法

    本文实例讲述了Python将阿拉伯数字转换为罗马数字的方法.分享给大家供大家参考.具体实现方法如下: def numToRomanNum(Num): """digital will be converted into Roman numerals,Ex: numToRomanNum(3999)""" if Num < 1 or Num > 3999: print 'The Num must in 1-3999' else: NumDi

  • python实现寻找最长回文子序列的方法

    本文实例为大家分享了python实现寻找最长回文子序列,这一类的问题可以使用动态规划的方法去做,我之前应该有几篇博文都是关于回文序列的求解的,正好有可以复用的代码就懒得再用别的方法写了,直接套用,思想还是滑窗切片,很简单就是运算会多点,下面是具体实现: #!usr/bin/env python #encoding:utf-8 ''''' __Author__:沂水寒城 功能:寻找最长回文子序列 ''' def slice_window(one_str,w=1): ''''' 滑窗函数 ''' r

  • 对python判断是否回文数的实例详解

    设n是一任意自然数.若将n的各位数字反向排列所得自然数n1与n相等,则称n为一回文数.例如,若n=1234321,则称n为一回文数:但若n=1234567,则n不是回文数. 上面的解释就是说回文数和逆序后的结果是相等的.这就是判断一个数值是否是回文数的标准. 代码也是根据这个思路来实现的. # -*- coding: utf-8 -*- """ Created on Sun Aug 5 09:01:38 2018 @author: FanXiaoLei ""

  • Python3.5实现的罗马数字转换成整数功能示例

    Python3.5实现的罗马数字转换成整数功能示例

    本文实例讲述了Python3.5实现的罗马数字转换成整数功能.分享给大家供大家参考,具体如下: 问题概述: 给定一个罗马数字 ,将罗马数字转换成整数. 如罗马数字I,II,III,IV,V分别代表数字 1, 2, 3, 4, 51,2,3,4,5. 首先要来了解一下罗马数字表示法,基本字符有 7 个:I.V.X.L.C.D.M,分别表示 1.5.10.50.100.500.1000. 在构成数字的时候,有下列规则: 1.相同的数字连写,所表示的数等于这些数字相加得到的数,如:III = 3: 2

  • Python3实现的判断回文链表算法示例

    本文实例讲述了Python3实现的判断回文链表算法.分享给大家供大家参考,具体如下: 问题: 请判断一个链表是否为回文链表. 方案一:指针法 class Solution: def isPalindrome(self, head): """ 判断一个链表是否是回文的,很自然的想法就是两个指针,一个指针从前往后走,一个指针从后往前走,判断元素值是否相同,这里要分几个步骤来进行求解: 1.找到链表长度的一半,用追赶法,一个指针一次走两步,一个指针一次走一步 2.将后一半数组转置

  • Python计算回文数的方法

    本文实例讲述了Python计算回文数的方法.分享给大家供大家参考.具体如下: 这里检查数字是不是回文数,用196算法生成一个数字的回文数 num = 905; def is_Palindrome(num): """ 判断一个数字是不是回文数,这里有些取巧了 :param num: :return: """ """ :param num: :return: """ temp = "

  • Python实现将罗马数字转换成普通阿拉伯数字的方法

    本文实例讲述了Python实现将罗马数字转换成普通阿拉伯数字的方法.分享给大家供大家参考,具体如下: 罗马数字,我们在某些电视中或者现实生活中都曾经看到过,近日,学习Python时,也遇到了罗马数字的解说,于是顺便写了一个小程序来练习罗马数字到我们日常生活普通数字之间的转换的小函数. 首先,咱们了解一下,罗马数字的潜在法则, 在罗马数字中,利用7个不同字母进行重复或者组合来表达各式各样的数字. I = 1 V = 5 X = 10 L = 50 C = 100 D = 500 M = 1000

  • python实现求最长回文子串长度

    给定一个字符串,求它最长的回文子串长度,例如输入字符串'35534321',它的最长回文子串是'3553',所以返回4. 最容易想到的办法是枚举出所有的子串,然后一一判断是否为回文串,返回最长的回文子串长度.不用我说,枚举实现的耗时是我们无法忍受的.那么有没有高效查找回文子串的方法呢?答案当然是肯定的,那就是中心扩展法,选择一个元素作为中心,然后向外发散的寻找以该元素为圆心的最大回文子串.但是又出现了新的问题,回文子串的长度即可能是基数,也可能好是偶数,对于长度为偶数的回文子串来说是不存在中心元

随机推荐