【Python】2つの文字列を共通の位置で分割して回文を作れるか判定するプログラム

問題の概要

同じ長さの2つの文字列 S と T が与えられたとき、両方の文字列を共通の位置で切断し、S の前半部分と T の後半部分をつなぎ合わせて回文（前から読んでも後ろから読んでも同じになる文字列）を作ることができるかどうかを判定します。

例えば、入力が S = "cat"、T = "dac" の場合、出力は True になります。文字列を「c」+「at」と「d」+「ac」に分割すると、「c」+「ac」（つまり "cac"）が回文になるためです。

アルゴリズムの手順

この問題を解くためには、以下の手順に従います。

• n := 文字列 a の長さ
• i := 0
• i < n かつ a[i] が b[n-i-1] と等しい間、次を繰り返します：
  • i := i + 1
• a[i から n-i-1 までの部分文字列] が回文であるか、b[i から n-i-1 までの部分文字列] が回文である場合に true を返します

考え方のポイント

先頭から順に、a の左側の文字と b の右側の文字を比較していきます。一致している限り、その部分はどちらの文字列を使っても回文として成立するため、そのままスキップできます。一致しなくなった時点で残った中央部分が、a または b のどちらか一方だけでも回文になっていれば、答えは True となります。

実装例

理解を深めるために、以下の Python 実装を見てみましょう。

class Solution:
    def solve(self, a, b):
        n = len(a)
        i = 0
        while i < n and a[i] == b[-i-1]:
            i += 1
        palindrome = lambda s: s == s[::-1]
        return palindrome(a[i:n-i]) or palindrome(b[i:n-i])
ob = Solution()
S = "cat"
T = "dac"
print(ob.solve(S, T))

入力

"cat","dac"

出力

True

計算量について

時間計算量は O(n) です。また、スライスによって一時的な文字列が生成されるため、空間計算量は O(n) となります。スライスを使わずインデックスで直接文字を比較すれば、空間計算量を O(1) に抑えることも可能です。