迴文子序列

 從字串 d 中找到所有迴文子序列，並最終輸出長度大於 1 的所有迴文子序列，以及最長的迴文子序列。

def cp(s):

  if s==s[::-1]:

    return True

  return False

d = '5612345432157'

dd = []

for i  in range(len(d)):

  for j in range(i+1,len(d)+1):

    dd.append(d[i:j])

r = []

for d in set(dd):

  m = len(d)//2

  if len(d)%2==1:

    for i in range(m+1):

      if cp(d[m-i:m+1+i]):r.append(d[m-i:m+1+i])

  else:

    for i in range(m):

      if cp(d[m-i-1:m+1+i]):r.append(d[m-i-1:m+1+i])

print('長度大於1的所有迴文子序列')

for i in set(r):

  if len(i)>1:

    print(i)

rlen = [len(i) for i in r]

print('最長迴文子序列')

print(r[ rlen.index(max(rlen))])

Output:

# 長度大於1的所有迴文子序列

# 2345432

# 454

# 34543

# 123454321

# 最長迴文子序列

# 123454321

主要部分的解釋：

1. cp(s) 函數：

• 這個函數用來檢查字串 s 是否為迴文。
• s[::-1] 是字串 s 的反轉。
• 如果 s 等於反轉後的 s，則表示這是一個迴文，回傳 True，否則回傳 False。

2. 生成所有子字串：

• d = '5612345432157' 是待處理的字串。
• 兩層 for 迴圈會生成字串 d 的所有子字串，並存入列表 dd 中。
  • 外層迴圈控制子字串的起點 i，內層迴圈控制終點 j。
  • 每次迭代會將 d[i:j] （從第 i 位到第 j-1 位的子字串）添加到 dd 列表中。

3. 查找迴文子序列：

• 使用 set(dd) 將 dd 中的重複子字串去除。
• 針對每一個子字串 d，先找到其中心位置 m，然後分別處理長度為奇數和偶數的子字串。
  • 奇數長度：從中心向兩邊擴展，檢查是否是迴文。如果是迴文，將該子字串添加到 r 列表中。
  • 偶數長度：從中間的兩個字元開始向兩邊擴展，檢查是否是迴文。如果是迴文，將該子字串添加到 r 列表中。

4. 輸出所有迴文子序列：

• 使用 set(r) 去除重複的迴文子序列，並打印出所有長度大於 1 的迴文子序列。

5. 找出最長的迴文子序列：

• 使用 rlen = [len(i) for i in r] 計算每個迴文子序列的長度，並用 max(rlen) 找到其中最長的迴文子序列的長度。
• 使用 rlen.index(max(rlen)) 找到最長迴文的索引，然後將其打印出來。

程式的邏輯：

1. 生成所有子字串：對字串 d 的每一個子字串進行處理，並將它們存入列表 dd 中。
2. 檢查迴文：針對每個子字串，使用中心擴展法檢查是否為迴文，並將迴文加入結果列表 r 中。
3. 輸出結果：
   • 輸出所有長度大於 1 的迴文子序列。
   • 找出最長的迴文子序列並輸出。

程式的執行流程：

1. 生成子字串：字串 5612345432157 的所有子字串被生成並去重。
2. 檢查迴文：所有可能的子字串被檢查是否為迴文，找到的迴文子序列被加入結果列表。
3. 輸出迴文：
   • 程式列出所有長度大於 1 的迴文子序列，如：2345432, 454, 34543, 123454321。
4. 最長迴文子序列：最長的迴文子序列是 123454321。

輸出結果：

長度大於1的所有迴文子序列
2345432
454
34543
123454321
最長迴文子序列
123454321

優化建議：

1. 使用 set 去重：目前使用 set(dd) 和 set(r) 避免重複迴文子序列，可以有效提升程式效率。
2. 中心擴展法：這個方法適用於檢查迴文子序列的效率較高。

這個程式成功地找出了所有迴文子序列並且找到了最長的迴文。