【Python】1文字を削除して別の文字列に変換できるか判定する方法

2つの文字列 s と t が与えられたとき、s から1文字だけ削除することで t と同じ文字列を作れるかどうかを判定する問題について解説します。

問題の例

たとえば、入力が以下の場合を考えてみましょう。

• s = "world"
• t = "wrld"

この場合、"world" から「o」を1文字削除すると "wrld" になるため、出力は True となります。

解決のアプローチ

この問題は、次の手順で解くことができます。

1. インデックス i を 0 で初期化し、文字列 s の長さを n として取得します。
2. i が n 未満である間、以下を繰り返します。
   • s の i 番目の文字を取り除いた文字列（前半部分と後半部分を連結）を temp として作成します。
   • temp が t と一致した場合、True を返します。
3. 一致しなければ i を1つ進めて処理を続けます。
4. すべての位置を試しても一致しなかった場合は、False を返します。

実装例

それでは、実際のコードを見てみましょう。

class Solution:
    def solve(self, s, t):
        i = 0
        n = len(s)
        while(i < n):
            temp = s[:i] + s[i+1:]
            if temp == t:
                return True
            i += 1
        return False

ob = Solution()
s = "world"
t = "wrld"
print(ob.solve(s, t))

入力

"world", "wrld"

出力

True

コードのポイント

このコードでは、スライス構文 s[:i] + s[i+1:] を使うことで、i 番目の文字だけを除外した新しい文字列を簡単に作成しています。ループで全ての位置を順番に試すため、計算量は O(n²) となりますが、シンプルで理解しやすい実装です。

より効率的な方法としては、両文字列の長さの差がちょうど1であることを先に確認し、最初に異なる文字が現れた位置を特定して比較する方法もあります。文字列が長い場合はこちらの方が高速に動作します。