Pythonで文字列を3つの回文に分割できるか判定するプログラム

文字列 s が与えられたとき、その文字列を3つの回文（palindrome）の部分文字列に分割できるかどうかを判定する問題を考えてみましょう。

たとえば、入力が s = "levelpopracecar" の場合、「level」「pop」「racecar」の3つに分割でき、これらはすべて回文であるため、出力は True になります。

解法のアプローチ

この問題は、動的計画法（DP）を用いて各部分文字列が回文かどうかを事前に計算しておくことで、効率的に解くことができます。手順は以下の通りです。

• n := 文字列 s の長さ

• dp := n × n の行列を作成し、すべて False で初期化する（dp[i][j] は「s[i..j] が回文であるか」を表す）

• i を n-1 から 0 まで 1 ずつ減らしながら繰り返す：

  • j を 0 から n-1 まで繰り返す：

    • i >= j の場合：

      • dp[i][j] := True（長さ1以下の部分文字列は常に回文）

    • s[i] と s[j] が等しい場合：

      • dp[i][j] := dp[i+1][j-1]（両端が一致し、かつ内側の部分文字列も回文であれば回文となる）

• i を 1 から n-1 まで、j を i+1 から n-1 まで繰り返し、dp[0][i-1]、dp[i][j-1]、dp[j][n-1] がすべて True であれば：

  • True を返す（3つの分割位置が見つかったことを意味する）

ポイントは、まず DP テーブルで「任意の区間が回文かどうか」をすべて求めておき、その後に2つの分割位置 i と j を全探索することです。これにより、文字列全体を [0, i-1]、[i, j-1]、[j, n-1] の3つの区間に分けたとき、それぞれが回文になっているかを O(1) で確認できます。計算量は O(n²) となります。

実装例

それでは、以下の Python 実装を見て理解を深めましょう。

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