Pythonを使用して最長のパリンドロームサブシーケンスの長さを見つけるプログラム

文字列が与えられたとします。長さが均一で、中央を除いて2つの連続する同じ文字を含まないパリンドロームサブシーケンスを見つける必要があります。このタイプの部分文字列の長さを出力として返す必要があります。

したがって、入力がs ='efeffe'のような場合、出力は4

偶数の長さのパリンドロームサブシーケンスが1つしかないため、出力は4です。文字列は長さ4の「effe」です。

これを解決するには、次の手順に従います-

• n：=sのサイズ

• dp：=1つのnx n 2d配列。ここで、各項目は（0、空白の文字列）の形式のペアです

• n-1から-1の範囲のiの場合、1ずつ減少します

  • i + 1からnの範囲のjについては、次のようにします

    • s[i]がs[j]と同じで、dp [i + 1、j-1]の文字列がs [i]でない場合、

      • dp [i、j]：=ペアを作成します（dp [i + 1、j-1] + 2、s [i]の最初の要素）

    • それ以外の場合

      • dp [i、j]：=ペアの最初の要素が最大になる（dp [i + 1、j]、dp [i、j-1]、dp [i + 1、j-1]）の中から選択します

    • dp [0、n-1]

      に格納されているペアの最初の要素を返します

理解を深めるために、次の実装を見てみましょう-

例

def solve(s):
   n = len(s)
   dp = [[(0, '')]*n for _ in range(n)]
   for i in range(n-1, -1, -1):
      for j in range(i+1, n):
         if s[i]== s[j] and dp[i+1][j-1][1] != s[i]:
            dp[i][j] = (dp[i+1][j-1][0] + 2, s[i])
         else:
            dp[i][j] = max(dp[i+1][j], dp[i][j-1], dp[i+1][j-1], key=lambda x: x[0])
   return dp[0][n-1][0]
print(solve('efeffe'))

入力

'efeffe'

出力

4