文字列をチェックするプログラムは、Pythonでは3つの回文に分割できます。

文字列sがあるとします。 sを3つの回文部分文字列に分割できるかどうかを確認する必要があります。

したがって、入力がs ="levelpopracecar"のような場合、"level"、 "pop"、 "racecar"のように分割できるため、出力はTrueになります。すべてがパリンドロームです。

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

• n：=sのサイズ

• dp：=次数nxnの行列でfalseで埋める

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

  • 0からn-1の範囲のjの場合、実行

    • i> =jの場合、

      • dp [i、j]：=True

    • それ以外の場合、s[i]がs[j]と同じである場合、

      • dp [i、j]：=dp [i + 1、j-1]

  • 1からn-1の範囲のiの場合、実行

    • i +1からn-1の範囲のjの場合、実行

      • dp [0、i-1]とdp [i、j-1]とdp [j、n-1]がすべて真の場合、

        • Trueを返す

• Falseを返す

例

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

def solve(s):
   n = len(s)

   dp = [[False] * n for _ in range(n)]
   for i in range(n-1, -1, -1):
      for j in range(n):
         if i >= j:
            dp[i][j] = True
         elif s[i] == s[j]:
            dp[i][j] = dp[i+1][j-1]
   for i in range(1, n):
      for j in range(i+1, n):
         if dp[0][i-1] and dp[i][j-1] and dp[j][n-1]:
            return True
   return False

s = "levelpopracecar"
print(solve(s))

入力

"levelpopracecar"

出力

True