Pythonで指定した単語を組み合わせて2文字の文字列を作成できるか判定する方法

長さ2の文字列 s と、すべての要素が長さ2の単語であるリスト w があるとします。このとき、w に含まれる単語を連結してできた文字列の中に、s が部分文字列として含まれるかどうかを判定する問題です。

例えば、s = "no"、w = ["ol", "on", "ni", "to"] の場合、出力は True になります。これは、「on」+「ol」のように単語を連結すると「onol」という文字列が作れ、その中に「no」が含まれているためです。

解法のアプローチ

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

• n := リスト w に含まれる単語の総数
• char_0 := False、char_1 := False として初期化
• i を 0 から n - 1 まで繰り返し処理を行う
  • w[i] が s と完全に一致する場合は True を返す
  • s[0]（s の先頭文字）が w[i][1]（w[i] の末尾文字）と一致する場合は char_0 := True にする
  • s[1]（s の末尾文字）が w[i][0]（w[i] の先頭文字）と一致する場合は char_1 := True にする
  • char_0 と char_1 が両方とも True になった場合は True を返す
• ループが終了しても条件を満たさなければ False を返す

このアルゴリズムのポイントは、ある単語の末尾文字が s の先頭文字と一致し、別の単語の先頭文字が s の末尾文字と一致していれば、その2つの単語を連結することで s を部分文字列として含む文字列を作れるという点です。計算量は O(n) となり、非常に効率的です。

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

実装例

def solve(s, w):
    n = len(w)
    char_0 = False
    char_1 = False
    for i in range(n):
        if w[i] == s:
            return True
        if s[0] == w[i][1]:
            char_0 = True
        if s[1] == w[i][0]:
            char_1 = True
        if char_0 and char_1:
            return True
    return False

s = "no"
w = ["ol", "on", "ni", "to"]
print(solve(s, w))

入力

"no", ["ol", "on", "ni", "to"]

出力

True

このように、リスト内の各単語を一度だけ走査することで、目的の文字列を作成可能かどうかを効率的に判定できます。単語そのものが s と一致するケースや、複数の単語を組み合わせるケースの両方に対応している点が特徴です。