Pythonで文字列がパターンで定義された文字の順序に従っているかを確認する方法

文字列 s と、パターンを表す別の文字列 t が与えられたとします。このとき、s に含まれる文字が、t で定義された順序どおりに並んでいるかどうかを判定します。なお、パターン t には重複する文字は含まれないものとします。

たとえば、s = "hello world"、t = "hw" という入力の場合、"h" の後ろに "w" が現れるため、出力は True になります。

解決のためのアプローチ

この問題は、以下の手順で解決できます。

• s の長さが t の長さより短い場合は、False を返します。
• i を 0 から len(t) - 2 の範囲で繰り返します。
  • x := t[i]、y := t[i + 1] とする
  • right := 文字列 s 内で x が最後に出現するインデックス
  • left := 文字列 s 内で y が最初に出現するインデックス
  • right が -1、または left が -1、または right > left の場合は False を返す
• すべてのチェックを通過したら True を返します。

それでは、実際の実装例を見て理解を深めましょう。

サンプルコード

def solve(s, t):
    if len(s) < len(t):
        return False

    for i in range(len(t) - 1):
        x = t[i]
        y = t[i + 1]

        right = s.rindex(x)
        left = s.index(y)

        if right == -1 or left == -1 or right > left:
            return False

    return True

s = "hello world"
t = "hw"
print(solve(s, t))

入力

"hello world", "hw"

出力

True

仕組みの解説

このアルゴリズムのポイントは、Python の文字列メソッド rindex() と index() を組み合わせている点です。rindex() は指定した文字が最後に出現する位置を、index() は最初に出現する位置をそれぞれ返します。

パターン内の隣接する 2 文字（x と y）について、「x の最後の出現位置」が「y の最初の出現位置」より後ろにあれば、文字の順序が崩れていることになります。このチェックをパターンのすべての隣接ペアに対して行うことで、文字列全体がパターンの順序に従っているかを効率的に検証できます。

なお、実際の Python では、対象の文字が見つからない場合、index() や rindex() は -1 を返す代わりに ValueError 例外を発生させる点に注意してください。実運用では try-except による例外処理や、事前に文字の存在確認を追加しておくと、より安全で堅牢なコードになります。