南强小屋 Design By 杰米
本文实例为大家分享了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,最长回文子序列
南强小屋 Design By 杰米
广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！ 如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！ 如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com
南强小屋 Design By 杰米
暂无python实现寻找最长回文子序列的方法的评论...
RTX 5090要首发 性能要翻倍！三星展示GDDR7显存
三星在GTC上展示了专为下一代游戏GPU设计的GDDR7内存。
首次推出的GDDR7内存模块密度为16GB，每个模块容量为2GB。其速度预设为32 Gbps（PAM3），但也可以降至28 Gbps，以提高产量和初始阶段的整体性能和成本效益。
据三星表示，GDDR7内存的能效将提高20%，同时工作电压仅为1.1V，低于标准的1.2V。通过采用更新的封装材料和优化的电路设计，使得在高速运行时的发热量降低，GDDR7的热阻比GDDR6降低了70%。