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

本文实例为大家分享了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] 

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