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

2つの文字列 s と t が与えられ、t はすべて大文字であるとします。次の操作を繰り返すことで、s を t に変換できるかどうかを判定する問題を考えてみましょう。

• 一部の小文字を大文字に変換する。
• すべての小文字を削除する。

たとえば、入力が s = "fanToM"、t = "TOM" の場合、出力は True になります。'o' を 'O' に変換し、残りの小文字をすべて削除すれば t と一致するためです。

解法のアプローチ

この問題は動的計画法(DP)を使って効率的に解けます。dp[i][j] を「s の先頭 i 文字を使って、t の先頭 j 文字を作れるかどうか」を表す真偽値として定義します。

具体的な手順は以下の通りです。

• n := s の長さ、m := t の長さとします。
• (n + 1) 行 × (m + 1) 列の行列 dp を作成し、すべて False で初期化します。
• dp[0][0] := True とします(空文字列から空文字列は必ず作れるため)。
• i を 0 から s の長さ - 1 まで繰り返します。
  • j を 0 から t の長さまで繰り返します。
    • dp[i][j] が True の場合:
      • j が t の長さ未満で、s[i] を大文字にしたものが t[j] と一致するなら、dp[i + 1][j + 1] := True とします(その文字を大文字化して採用)。
      • s[i] が小文字なら、dp[i + 1][j] := True とします(その文字を削除してスキップ)。
• 最後に dp[n][m] を返します。

実装例

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

def solve(s, t):
    n = len(s)
    m = len(t)
    dp = [[False for i in range(m + 1)] for i in range(n + 1)]
    dp[0][0] = True
    for i in range(len(s)):
        for j in range(len(t) + 1):
            if dp[i][j]:
                # 現在の文字を大文字に変換して採用する場合
                if j < len(t) and s[i].upper() == t[j]:
                    dp[i + 1][j + 1] = True
                # 小文字を削除してスキップする場合
                if not s[i].isupper():
                    dp[i + 1][j] = True
    return dp[n][m]

s = "fanToM"
t = "TOM"
print(solve(s, t))

入力

"fanToM", "TOM"

出力

True

まとめ

このアルゴリズムの計算量は O(n × m) です。各文字について「大文字に変換して使う」か「削除する」かの選択をDPテーブルで管理することで、文字列変換の可否を正確に判定できます。このパターンは部分一致系の文字列問題で頻出するため、覚えておくとさまざまな場面で役立ちます。