本文实例为大家分享了python实现寻找最长回文子序列，这一类的问题可以使用动态规划的方法去做，我之前应该有几篇博文都是关于回文序列的求解的，正好有可以复用的代码就懒得再用别的方法写了，直接套用，思想还是滑窗切片，很简单就是运算会多点，下面是具体实现：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
#!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]
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/Together_CZ/article/details/76694242
