本文實(shí)例為大家分享了python實(shí)現(xiàn)尋找最長回文子序列，這一類的問題可以使用動(dòng)態(tài)規(guī)劃的方法去做，我之前應(yīng)該有幾篇博文都是關(guān)于回文序列的求解的，正好有可以復(fù)用的代碼就懶得再用別的方法寫了，直接套用，思想還是滑窗切片，很簡單就是運(yùn)算會(huì)多點(diǎn)，下面是具體實(shí)現(xiàn)：

#!usr/bin/env python #encoding:utf-8  ''''' __Author__:沂水寒城 功能：尋找最長回文子序列 '''  def slice_window(one_str,w=1):   '''''   滑窗函數(shù)   '''   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):    '''''   輸入一個(gè)字符串列表，判斷是否為回文序列   '''    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):   '''''   主函數(shù),尋找最長回文子序列   '''   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) 

結(jié)果如下：

abcdcba 
abcba 
bb 
abcba 
[Finished in 0.3s] 

以上就是本文的全部內(nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持武林站長站。