Pythonで文字列を別の文字列に変換できるか判定する方法

問題の概要

同じ長さを持つ2つの文字列 str1 と str2 が与えられます。0回以上の「変換」操作を繰り返すことで、str1 を str2 へ変換できるかどうかを判定してください。

ここでいう1回の変換とは、str1 内に出現するある1種類の文字を、すべて別の小文字の英字へ一括して置き換える操作を指します。例えば、文字 'a' をすべて 'c' に変えるといった具合です。

具体例

str1 = "aabcc"、str2 = "ccdee" の場合、出力は True になります。手順としては、まず 'c' を 'e' に変換し、次に 'b' を 'd' に、最後に 'a' を 'c' に変えればよいためです。

このとき重要なのは変換の順序です。もし先に 'a' を 'c' に変えてしまうと、元から存在していた 'c' まで一緒に変わってしまい、目的の文字列にたどり着けなくなります。

解法のアプローチ

この問題は、次の2つの関数を組み合わせて解きます。

ステップ1：連続文字数を圧縮する compress() 関数

• compress() は文字列 s を引数として受け取ります。
• n は s の長さ、a は結果を格納する空のリスト、count は連続文字数を数えるカウンター（初期値 1）です。
• i を 1 から n-1 まで走査します。
  ・s[i] が直前の文字 s[i-1] と異なる場合は、現在の count をリスト a の末尾に追加し、count を 1 に戻します。
  ・同じ文字が続いている場合は、count を 1 増やします。
• ループを抜けたら最後の count を a に追加し、a を返します。

これにより、例えば "aabcc" は [2, 1, 2] のように「各文字の連続回数の列（ランレングス圧縮）」へと変換されます。

ステップ2：変換可能性を判定する canConvert() 関数

• str1 と str2 をそれぞれ compress() に通し、ランレングス列 a と b を求めます。
• n は a のサイズ、m は b のサイズ、d は str2 に登場する異なる文字を記録するための辞書（マップ）です。
• n を n と m の最小値に更新し、i を 0 から順に比較します。a[i] > b[i] となる箇所が1つでもあれば False を返します。これは、str1 側の連続区間が対応する str2 側の区間より長いと、文字の境界位置が一致しなくなり変換が不可能になるためです。
• 続いて str2 の各文字を走査し、辞書 d に未登録の文字を登録していきます。
• 最後に、「26 - len(d)」が 0 以外（＝str2 が26種類の英字をすべて使い切っていない）、または str1 と str2 が完全一致している場合に True を返し、それ以外は False を返します。

なぜ「26 - len(d)」を確認するのかというと、英小文字は全部で26種類しかないからです。str2 がすべてのアルファベットを使用している場合、変換の中継地点として使える「予備の文字」が存在せず、順序をどう工夫しても変換が行き詰まる恐れがあります。

実装例

以下のコードで実際の動作を確認できます。

class Solution(object):
    def compress(self, s):
        n = len(s)
        a = []
        count = 1
        for i in range(1, n):
            if s[i] != s[i-1]:
                a.append(count)
                count = 1
            else:
                count += 1
        a.append(count)
        return a

    def canConvert(self, str1, str2):
        a = self.compress(str1)
        b = self.compress(str2)
        n = len(a)
        m = len(b)
        d = {}
        n = min(n, m)
        i = 0
        while i < n:
            if a[i] > b[i]:
                return False
            i += 1
        for ch in str2:
            if ch not in d:
                d[ch] = 1
        return True if 26 - len(d) or str1 == str2 else False

ob = Solution()
print(ob.canConvert("aabcc", "ccdee"))

入力

"aabcc", "ccdee"

出力

True

まとめ

本手法では、ランレングス圧縮によって両文字列の構造を比較し、辞書によって使用文字の種類を管理することで変換の可否を判定しています。文字列の長さを N とすると、計算量は O(N) となり、効率的に処理できます。