Pythonで2つの文字列が等価かどうかを再帰的に判定する方法

問題の概要

同じ長さを持つ2つの文字列 s と t があるとします。このとき、s と t が「等価」であるかどうかを判定する必要があります。等価とみなされる条件は以下の通りです。

• 両者の文字列が完全に一致している。または、
• 文字列 s を同じサイズの2つの連続する部分文字列 s1 と s2 に分割し、同様に t も t1 と t2 に分割した場合、次のいずれかが成り立てばよい:
  • s1 が t1 と再帰的に等価であり、かつ s2 が t2 と再帰的に等価である
  • s1 が t2 と再帰的に等価であり、かつ s2 が t1 と再帰的に等価である

具体例

たとえば、入力が s = "ppqp"、t = "pqpp" の場合、出力は True になります。

s を s1 = "pp"、s2 = "qp" に分割し、t を t1 = "pq"、t2 = "pp" に分割すると、まず s1 = t2 が成り立ちます。さらに s2 と t1 をそれぞれ s21 = "q"、s22 = "p"、t11 = "p"、t12 = "q" に分割すると、s21 = t12 かつ s22 = t11 となるため、再帰的に等価であることが確認できます。

解法のアプローチ

この問題は、各文字列を「正規形」に変換してから比較することで効率的に解けます。手順は以下の通りです。

1. 関数 util() を定義します。引数として文字列 s を受け取ります。
2. s の長さが奇数の場合、それ以上分割できないため s をそのまま返します。
3. s の左半分に対して util() を再帰的に適用し、結果を left とします。
4. 右半分についても同様に処理し、結果を right とします。
5. left + right と right + left のうち、辞書順で小さい方を返します。これにより、部分文字列の入れ替えによって生じうるすべてのパターンが同一の正規形にまとめられます。
6. メイン処理では、util(s) と util(t) が一致すれば True、そうでなければ False を返します。

実装コード

def util(s):
    if len(s) & 1 != 0:
        return s

    left = util(s[0:int(len(s) / 2)])
    right = util(s[int(len(s) / 2):len(s)])

    return min(left + right, right + left)

def solve(s, t):
    return util(s) == util(t)

s = "ppqp"
t = "pqpp"
print(solve(s, t))

入力

"ppqp", "pqpp"

出力

True

計算量について

このアルゴリズムの時間計算量は O(n log n) です。文字列を毎回半分に分割しながら再帰処理を行うため、再帰の深さは O(log n)、各レベルでの文字列結合と比較に O(n) かかるためです。メモリ使用量も同様に O(n log n) となります。

まとめ

文字列を再帰的に半分に分割し、辞書順で最小の並びに正規化してから比較するというシンプルな発想により、複雑な等価性の判定問題をエレガントに解決できます。この手法は、分割統治法の典型的な応用例としても学習価値が高いでしょう。