Pythonで2つの文字列を分割して回文を作成できるか判定するプログラム

問題の概要

同じ長さを持つ2つの文字列 a と b があるとします。あるインデックスを1つ選び、その位置で両方の文字列を同時に分割します。すると、a は前半部分 a_pref と後半部分 a_suff に(a = a_pref + a_suff)、b も同様に b_pref と b_suff に(b = b_pref + b_suff)分けられます。

このとき、「a_pref + b_suff」または「b_pref + a_suff」という組み合わせのどちらかが回文(前から読んでも後ろから読んでも同じ文字列)になるかどうかを判定するのが目的です。なお、分割位置によっては片方が空文字列になっても構いません。

具体例

入力が a = "pqrst"、b = "turqp" の場合、出力は True になります。これは、a を ["pq", "rst"]、b を ["tu", "rqp"] のように分割すると、a_pref("pq") と b_suff("rqp") を連結した "pqrqp" が回文になるためです。

解法のアプローチ

この問題は、次の手順で効率よく解くことができます。

• ペアのリスト [(a, b), (b, a)] の各ペア (x, y) について、以下の処理を行います。
• i := 0、j := xの長さ - 1 として初期化します。
• x[i] と y[j] が一致している間、かつ i < xの長さ かつ j > 0 の間、i を1増やしながら j を1減らします(両端から内側へ照合)。
• midx := x のインデックス i から j までの部分文字列とします。
• midy := y のインデックス i から j までの部分文字列とします。
• midx または midy のどちらかが回文であれば、True を返します。

すべてのペアで条件を満たさなかった場合は、False を返します。

この手法のポイントは、まず外側から一致する文字をできるだけ多く取り除き、残った中央部分がどちらかの文字列で回文になっているかを確認する点です。これにより、全パターンを総当たりする必要がなく、計算量は O(n) で済みます。

実装例(Python)

それでは、実際のコードを見てみましょう。

def solve(a, b):
   for x, y in [[a, b], [b, a]]:
       i, j = 0, len(x) - 1
       while x[i] == y[j] and i<len(x) and j>0:
           i += 1
           j -= 1
       midx = x[i:j+1]
       midy = y[i:j+1]
       if (midx == midx[::-1] or midy == midy[::-1]):
          return True
   return False

a = "pqrst"
b = "turqp"
print(solve(a, b))

入力

"pqrst", "turqp"

出力

True

コードの解説

このプログラムでは、(a, b) と (b, a) の両方向について処理を行うことで、「a_pref + b_suff」と「b_pref + a_suff」の両方のパターンを網羅的にチェックしています。whileループで両端から文字を比較して一致する範囲を特定し、スライス操作 x[i:j+1] で中央部分を取り出します。回文判定には s[::-1](文字列を反転したもの)との比較を利用しており、シンプルかつ高速に動作します。