Pythonで1文字だけ異なる単語のペアが存在するかどうかを判定するプログラム

問題概要

すべて同じ長さの小文字文字列からなるリスト words が与えられたとします。このリストの中に、1文字だけが異なる2つの文字列が存在するかどうかを判定するのが今回の課題です。

例えば、入力が words = ["seed", "pick", "lick", "root", "live"] の場合、「pick」と「lick」は先頭以外の文字が完全に一致しており、1文字だけ異なるため、出力は True になります。

解決アプローチ

この問題は、各単語から1文字をワイルドカード「*」に置き換えたパターンを生成し、そのパターンがすでに登録済みかどうかを確認することで効率的に解決できます。手順は以下の通りです。

• 空のセット s を用意する
• words 内の各 word について処理を行う:
  • 各インデックス i と文字 w に対して:
    • word[:i] + "*" + word[i+1:] というパターンが s に既に存在すれば True を返す
    • 存在しない場合は、そのパターンを s に追加する
• ループが完了しても見つからなければ False を返す

実装例

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

def solve(words):
    s = set()
    for word in words:
        for i, w in enumerate(word):
            if word[:i] + "*" + word[i + 1 :] in s:
                return True
            else:
                s.add(word[:i] + "*" + word[i + 1 :])

    return False

words = ["seed", "pick", "lick", "root", "live"]
print(solve(words))

入力

["seed", "pick", "lick", "root", "live"]

出力

True

計算量について

このアルゴリズムの時間計算量は O(n × m²) です(ここで n は単語数、m は各単語の長さ)。各単語ごとに m 個のパターンを生成し、パターンの作成やセットへの検索・追加にそれぞれ O(m) かかるためです。

もしすべての単語ペアを直接比較する方式を採ると、計算量は O(n² × m) となり、単語数が多い場合に非効率になります。ワイルドカードパターンとセットを組み合わせることで、大幅な高速化が実現できるのがこの手法のポイントです。