脚本之家,脚本语言编程技术及教程分享平台!
分类导航

Python|VBS|Ruby|Lua|perl|VBA|Golang|PowerShell|Erlang|autoit|Dos|bat|

服务器之家 - 脚本之家 - Python - python实现寻找最长回文子序列的方法

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

2021-02-28 00:17Together_CZ Python

这篇文章主要为大家详细介绍了python实现寻找最长回文子序列的方法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

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

延伸 · 阅读

精彩推荐