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

蓝鲸

发布时间：2026-10-13 | 6人浏览过

原创

本文介绍利用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)

程序运行结果如下所示：