Pythonで最初の文字列の最小インデックスに存在する2番目の文字列の文字を検索する方法

2つの文字列 str と patt があるとします。この課題では、str の中で最も小さいインデックス（先頭に近い位置）に現れる patt 内の文字を特定します。もし patt のどの文字も str に存在しない場合は、-1 を返します。

たとえば、入力が str = "helloworld"、patt = "wor" の場合、出力は 'o' になります。これは 'w' がインデックス 5、'o' がインデックス 4、'r' がインデックス 7 に存在しており、その中で最も小さいインデックスを持つのが 'o' だからです。

アルゴリズムの手順

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

1. 外側のループで、変数 i を 0 から patt のサイズまで順に処理します。
2. 内側のループで、変数 j を 0 から Str のサイズまで順に処理します。
3. patt[i] が Str[j] と一致し、かつ j が現在の minimum_index より小さい場合は、minimum_index を j に更新し、内側のループを抜けます。
4. すべてのループが終了した後、minimum_index が初期値 10⁹ と異なる（＝一致する文字が見つかった）場合は、Str[minimum_index] を返します。
5. 一致する文字が見つからなかった場合は、-1 を返します。

ここで minimum_index の初期値を非常に大きい値 10⁹ としているのは、「まだ一致する文字が見つかっていない」状態を表すためです。

実装例

理解を深めるために、以下の実装例を見てみましょう。

def get_min_index_char(Str, patt):
    minimum_index = 10**9
    for i in range(len(patt)):
        for j in range(len(Str)):
            if (patt[i] == Str[j] and j < minimum_index):
                minimum_index = j
                break
    if (minimum_index != 10**9):
        return Str[minimum_index]
    else:
        return -1

Str = "helloworld"
patt = "wor"
print(get_min_index_char(Str, patt))

入力

"helloworld", "wor"

出力

o

計算量について

このアルゴリズムは、patt の各文字に対して Str 全体を走査するため、時間計算量は O(n × m) となります（n は Str の長さ、m は patt の長さ）。ただし、一致する文字が見つかった時点で内側のループを break しているため、実際の処理はこれよりも高速に終わるケースが多くあります。

より Pythonic な書き方

Python の組み込み関数を活用すると、同じ処理をより簡潔に記述できます。

def get_min_index_char(Str, patt):
    candidates = [ch for ch in patt if ch in Str]
    return min(candidates, key=Str.index) if candidates else -1

print(get_min_index_char("helloworld", "wor"))  # 出力: o

このコードでは、まずリスト内包表記で Str に存在する patt の文字だけを抽出し、min() 関数の key 引数に Str.index を指定することで、Str 内での出現位置が最も小さい文字を取得しています。可読性が高く、実務でもおすすめの書き方です。