Pythonで同じ位置の1文字だけが異なる文字列ペアが存在するか判定するプログラム

本記事では、長さがすべて同じである複数の文字列を含む配列が与えられたとき、その中に「同じ位置でちょうど1文字だけ異なる」2つの文字列のペアが存在するかどうかを判定する方法を解説します。条件を満たすペアが存在すれば True を返し、存在しなければ False を返します。

問題の例

たとえば、入力が dict = ['pqrs', 'prqs', 'paqs'] の場合を考えてみましょう。このとき出力は True になります。

理由は、これら3つの文字列はすべてインデックス1(2番目)の文字だけが互いに異なっているためです。つまり、どの2つのペアを選んでも、必ず同じ位置で1文字の違いが生じます。

• pqrs と prqs:インデックス1が「q」と「r」で異なる
• pqrs と paqs:インデックス1が「q」と「a」で異なる
• prqs と paqs:インデックス1が「r」と「a」で異なる

解法のアプローチ

この問題は「マスク処理(パターン化)」とハッシュセットを組み合わせることで効率的に解けます。各文字列について、1文字ずつ「.」に置き換えたパターンを作成し、そのパターンがすでに登録済みであれば、同じ位置で1文字だけ異なるペアが存在することを意味します。

具体的な手順は以下の通りです。

• seens := 空のセット(集合)を用意する
• dict 内の各単語 word に対して以下を繰り返す:
  • 各インデックス i と文字 c に対して:
    • masked_word := インデックス i の文字を「.」に置き換えた文字列を作成する
    • masked_word がすでに seens に存在する場合 → True を返す
    • 存在しない場合 → masked_word を seens に追加する
• すべての単語を処理しても見つからなければ False を返す

Pythonでの実装例

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

def solve(dict):
    seens = set()
    for word in dict:
        for i, c in enumerate(word):
            masked_word = word[:i] + '.' + word[i+1:]
            if masked_word in seens:
                return True
            else:
                seens.add(masked_word)
    return False

print(solve(['pqrs', 'prqs', 'paqs']))

入力

['pqrs', 'prqs', 'paqs']

出力

True

計算量について

文字列の個数を n、各文字列の長さを m とすると、時間計算量は O(n × m) となります。各文字列に対して m 個のマスク済みパターンを生成し、セットへの挿入・検索は平均 O(1) で行えるためです。空間計算量も同様に O(n × m) となり、非常に効率的なアルゴリズムといえます。