【Python】文字列を回文に分割する方法の数を求めるアルゴリズムと実装

文字列 s が与えられたとき、その文字列を「すべての部分が回文になるように」分割する方法が何通りあるかを求める問題について解説します。

回文とは、前から読んでも後ろから読んでも同じになる文字列のことです。例えば「x」「yy」「xyyx」などはいずれも回文です。

問題の例

入力が s = "xyyx" の場合、出力は 3 になります。これは以下の3通りの分割方法が存在するためです。

• ["x", "yy", "x"]
• ["x", "y", "y", "x"]
• ["xyyx"]

解法のアプローチ(動的計画法)

この問題は動的計画法(DP)を使って効率的に解くことができます。ここでは、table[i] を「文字列の先頭から i 文字目までを回文に分割する方法の数」と定義して計算を進めます。

アルゴリズムの手順

1. n := 文字列 s の長さ
2. table := サイズ n+1 のリストを作成し、すべて 0 で初期化
3. table[0] := 1(空文字列の分割方法は1通りとみなす)
4. i を 0 から n まで繰り返す:
   • j を 0 から i-1 まで繰り返す:
     • sub := s[j:i](インデックス j から i までの部分文字列)
     • もし sub が回文であれば、table[i] := table[i] + table[j]
5. table の最後の要素を返す

Pythonでの実装例

class Solution:
   def solve(self, s):
      n = len(s)
      table = [1] + [0] * n
      for i in range(n + 1):
         for j in range(i):
            sub = s[j:i]
            if sub == sub[::-1]:
               table[i] += table[j]
      return table[-1]

ob = Solution()
s = "xyyx"
print(ob.solve(s))

入力

"xyyx"

出力

3

コードのポイント

回文判定には sub == sub[::-1] という比較を使用しています。Python のスライス [::-1] は文字列を逆順にする操作なので、元の文字列と逆順の文字列が一致すれば、その部分文字列は回文であると判断できます。

計算量は O(n³) となります(n は文字列の長さ)。これは二重ループの中で部分文字列の切り出しと回文判定を行っているためです。文字列が長くなる場合は、事前に回文判定用のテーブルを作成しておくことで高速化することも可能です。