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

yipeiwu_com6年前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] 

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持【听图阁-专注于Python设计】。

相关文章

Python选择网卡发包及接收数据包

当一台计算机上有多个网卡时,需要选择对应IP地址的网卡进行发送数据包或者接受数据包。 1、选择网卡发包(应用scapy): plface=conf.route.route("××.×...

在Python函数中输入任意数量参数的实例

有时候,预先不知道函数需要接受多少个实参,好在Python允许函数从调用语句中调用语句中收集任意数量的实参。在参数前加上*号。 来看一个制作披萨的函数,它需要接受很多配料,但你无法预先确...

详解python使用turtle库来画一朵花

详解python使用turtle库来画一朵花

看了群主最后成像的图片,应该是循环了36次画方框,每次有10度的偏移。 当然不能提前看答案,自己试着写代码。 之前有用过海龟画图来画过五角星、奥运五环、围棋盘等,所以感觉不难。 #...

python二进制读写及特殊码同步实现详解

python对二进制文件的操作需要使用bytes类,直接写入整数是不行的,如果试图使用f.write(123)向文件中以二进制写入123,结果提示参数不是bytes类型。 impor...

Python将图片转换为字符画的方法

Python将图片转换为字符画的方法

最近在学习Python,看到网上用Python将图片转换成字符画便来学习一下 题目意思是,程序读入一个图片,以txt格式输出图片对应的字符画,如图所示: 以下是Python代码:...