Pythonで2つの文字列を交互に組み合わせて目的の文字列を形成できるか判定するプログラム

2つの文字列 s と t、そしてもう1つの文字列 r が与えられたとき、s と t の文字をそれぞれの並び順を崩さずに交互に組み合わせることで、r を作れるかどうかを判定する問題を考えます。これは「インターリービング(interleaving)」と呼ばれる典型的な文字列操作の問題です。

たとえば、入力が s = "xyz"、t = "mno"、r = "xymnoz" の場合、出力は True になります。「xymnoz」は「xyz」と「mno」の文字を順番に交互につなぎ合わせることで形成できるからです。

解決のためのアプローチ

この問題は再帰関数を使って、以下の手順で解くことができます。

• 関数 solve() を定義します。引数として s、t、r を受け取ります。
• s、t、r がすべて空であれば True を返します。
• r だけが空の場合は False を返します。
• s が空の場合、t と r が一致していれば True、そうでなければ False を返します。
• t が空の場合、s と r が一致しているかどうかをそのまま返します。
• s[0] と r[0] が一致する場合、solve(s[1:], t, r[1:]) の結果が True であれば True を返します。
• t[0] と r[0] が一致する場合、solve(s, t[1:], r[1:]) の結果が True であれば True を返します。
• いずれの条件も満たさない場合は False を返します。

それでは、実際の実装例を見ていきましょう。

実装例(Python)

class Solution:
    def solve(self, s, t, r):
        if not s and not t and not r:
            return True
        if not r:
            return False
        if not s:
            return t == r
        if not t:
            return s == r
        if s[0] == r[0] and self.solve(s[1:], t, r[1:]):
            return True
        if t[0] == r[0] and self.solve(s, t[1:], r[1:]):
            return True
        return False

ob = Solution()
s = "xyz"
t = "mno"
r = "xymnoz"
print(ob.solve(s, t, r))

入力

"xyz", "mno", "xymnoz"

出力

True

コードのポイントと計算量

この再帰的なアプローチでは、各ステップで s 側と t 側のどちらの先頭文字を採用するかを両方試すため、最悪の場合の時間計算量は O(2^(m+n)) になります(m、n はそれぞれ s、t の長さです)。

ただし、同じ状態が何度も再計算されるため、メモ化(functools.lru_cache など)を導入すれば、時間計算量を O(m × n) まで大幅に改善できます。扱う文字列が長くなる場合は、デコレータによるキャッシュの追加や、動的計画法(DP)テーブルを使った実装への書き換えを検討するとよいでしょう。