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

本文实例为大家分享了python实现寻找最长回文子序列，这一类的问题可以使用动态规划的方法去做，我之前应该有几篇博文都是关于回文序列的求解的，正好有可以复用的代码就懒得再用别的方法写了，直接套用，思想还是滑窗切片，很简单就是运算会多点，下面是具体实现：

#!usr/bin/env python
#encoding:utf-8 

'''''
__Author__:沂水寒城
功能：寻找最长回文子序列
''' 

def slice_window(one_str,w=1):
  '''''
  滑窗函数
  '''
  res_list=[]
  for i in range(0,len(one_str)-w+1):
    res_list.append(one_str[i:i+w])
  return res_list 

def is_huiwen(one_str_list):
  '''''
  输入一个字符串列表，判断是否为回文序列
  '''
  if len(one_str_list)==1:
    return True
  else:
    half=len(one_str_list)/2
    if len(one_str_list)%2==0:
      first_list=one_str_list[:half]
      second_list=one_str_list[half:]
    else:
      first_list=one_str_list[:half]
      second_list=one_str_list[half+1:]
    if first_list==second_list[::-1]:
      return True
    else:
      return False  

def find_longest_sub_palindrome_str(one_str):
  '''''
  主函数,寻找最长回文子序列
  '''
  all_sub=[]
  for i in range(1,len(one_str)):
    all_sub+=slice_window(one_str,i)
  all_sub.append(one_str)
  new_list=[]
  for one in all_sub:
    if is_huiwen(list(one)):
      new_list.append(one)
  new_list.sort(lambda x,y:cmp(len(x),len(y)),reverse=True)
  print new_list[0] 

if __name__ == '__main__':
  one_str_list=['uabcdcbaop','abcba','dmfdkgbbfdlg','mnfkabcbadk']
  for one_str in one_str_list:
    find_longest_sub_palindrome_str(one_str)

结果如下：

abcdcba 
abcba 
bb 
abcba 
[Finished in 0.3s]

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • 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

  • 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

  • 对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实现的判断回文链表算法示例

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

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

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

  • 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

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

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

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

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

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

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

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

  • Python计算回文数的方法

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

随机推荐