Pythonで「A」と「B」の移動制約のもと、ある文字列を別の文字列へ変換できるか判定する方法

問題の概要

「A」「B」「#」の3種類の文字だけで構成された2つの文字列 s と t が与えられます。ここで、次のルールに従う操作によって s を t へ変換できるかどうかを判定するのが、この記事のテーマです。

• 「A」は左方向にしか移動できない
• 「B」は右方向にしか移動できない
• 「A」と「B」は互いに交差(追い越し)できない

例として、s = '##AB##B'、t = 'A###B#B' という入力を考えてみましょう。この場合の出力は True になります。s 内の A は左端の位置へスムーズに移動でき、中央の B も1ステップ右へ動けるためです。

解法の考え方

この問題は、貪欲法(グリーディ法)によるマッチングで解くことができます。手順は以下の通りです。

1. s と t をそれぞれ文字のリストに変換します。
2. 両者の長さが異なる場合は False を返します。
3. s と t に含まれる「A」の個数、または「B」の個数が一致しない場合も False を返します。
4. s の各位置 i について、s[i] が「#」でない場合は、t を先頭から走査し、最初に一致する文字を探します。
   • t[j] が s[i] と異なる文字で、かつ「#」でもない場合は False を返します。
   • t[j] が s[i] と一致したら、その位置を「#」で埋めて使用済みにします。
   • s[i] が「A」なのに i < j の場合(A が右へ移動することになる)は False を返します。
   • s[i] が「B」なのに i > j の場合(B が左へ移動することになる)は False を返します。
   • マッチングが完了したら内側のループを抜けます。
5. すべての文字が条件を満たしていれば True を返します。

重要なポイントは、「A」の移動後の位置 j は元の位置 i 以下(j ≤ i)である必要があり、「B」の移動後の位置 j は元の位置 i 以上(j ≥ i)である必要がある点です。この条件を満たさないペアが1つでも存在すれば、変換は不可能と判断できます。

Pythonでの実装例

それでは、上記のアルゴリズムをPythonで実装してみましょう。

def solve(s, t):
    s = list(s)
    t = list(t)
    if len(s) != len(t):
        return False
    if s.count('A') != t.count('A') or s.count('B') != t.count('B'):
        return False
    for i in range(len(s)):
        if s[i] != '#':
            for j in range(len(t)):
                if (t[j] != s[i]) and t[j] != '#':
                    return False
                if t[j] == s[i]:
                    t[j] = '#'
                    if s[i] == 'A' and i < j:
                        return False
                    if s[i] == 'B' and i > j:
                        return False
                    break
    return True

s = '##AB##B'
t = 'A###B#B'
print(solve(s, t))

入力

'##AB##B', 'A###B#B'

出力

True

計算量の目安

このアルゴリズムの時間計算量は O(n²) です。外側のループで s の各文字を確認し、内側のループで t を走査するためです。空間計算量は O(n) となり、文字列をリストに変換する分だけメモリを使用します。

より高速に処理したい場合は、あらかじめ t 内の「A」と「B」の位置インデックスをそれぞれキューに記録しておき、s を走査しながら対応する位置と順番に比較する方法(O(n))も有効です。