Python3最长回文子串算法示例

yipeiwu_com6年前Python基础

本文实例讲述了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程序设计有所帮助。

相关文章

python之信息加密题目详解

1.贴题 题目来自PythonTip 信息加密 给你个小写英文字符串a和一个非负数b(0<=b<26), 将a中的每个小写字符替换成字母表中比它大b的字母。这里将字母表...

Flask实现图片的上传、下载及展示示例代码

Flask实现图片的上传、下载及展示示例代码

用Flask处理图片非常容易,这一篇学习一下图片的上传、下载及展示。还是以实例代码演示为主。 首先,实现一个简单的上传(过程中未做任何处理,只是为了演示) 点击选择图片,输入李四:...

Python语言实现获取主机名根据端口杀死进程

推荐阅读:使用python检测主机存活端口及检查存活主机 下面给大家分享使用python语言实现获取主机名根据端口杀死进程代码。 ip=os.popen("ifconfig eth0...

Pytorch 神经网络—自定义数据集上实现教程

Pytorch 神经网络—自定义数据集上实现教程

第一步、导入需要的包 import os import scipy.io as sio import numpy as np import torch import torch.nn...

详解Python3的TFTP文件传输

详解Python3的TFTP文件传输

TFTP文件传输 功能: 1、获取文件列表 2、上传文件 3、下载文件 4、退出 第一部分,TftpServer部分。 ①导入相关模块 from socket import * im...