C++で解く最短単語距離 II：2単語間の最小距離を高速に求める実装

問題の概要

コンストラクタで単語のリストを受け取るクラスを考えます。このクラスには、2つの単語 word1 と word2 を引数に取り、リスト内における両者の最短距離を返すメソッドが備わっています。重要なのは、このメソッドが異なる引数の組み合わせで何度も繰り返し呼び出されるという点です。そのため、呼び出しごとにリスト全体を毎回走査するのではなく、事前処理によって高速な照会を実現する設計が求められます。

たとえば、words = ["practice", "makes", "perfect", "skill", "makes"] というリストがあるとします。

word1 = "skill"、word2 = "practice" という入力に対しては、出力は 3 となります。

解法のアイデア：ハッシュマップ＋2ポインタ法

各単語がリスト内のどの位置に出現したかを、構築時にハッシュマップへ記録しておきます。こうすると、shortest() が呼ばれた際は、それぞれの単語の出現位置リスト（昇順に整列済み）同士を比較するだけで済みます。具体的な手順は次のとおりです。

• キーを単語、値を出現位置のベクトルとするマップ m を定義します。
• コンストラクタで単語配列 words を受け取ります。
  i を 0 から words.size() − 1 まで1ずつ増やしながら、m[words[i]] の末尾にインデックス i を追加していきます。
• 関数 shortest(word1, word2) を定義し、arr1 = m[word1]、arr2 = m[word2] として位置リストを取得します。
• i = 0、j = 0、ret = INT_MAX（無限大扱い）で初期化します。
• i < arr1.size() かつ j < arr2.size() の間、以下を繰り返します。
  ・ret を、ret と |arr1[i] − arr2[j]| の小さい方で更新します。
  ・arr1[i] < arr2[j] なら i を、そうでなければ j を1進めます。
• 最後に ret を返します。

両方の位置リストが昇順にソートされているため、「より小さい側のインデックスを持つポインタ」だけを進めていけば、最小距離のペアを見逃すことなく探索できます。ここが2ポインタ法のポイントです。

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;

class WordDistance {
public:
    unordered_map<string, vector<int>> m;

    WordDistance(vector<string>& words) {
        for (int i = 0; i < (int)words.size(); i++) {
            m[words[i]].push_back(i);
        }
    }

    int shortest(string word1, string word2) {
        vector<int>& arr1 = m[word1];
        vector<int>& arr2 = m[word2];
        int i = 0, j = 0;
        int ret = INT_MAX;
        while (i < (int)arr1.size() && j < (int)arr2.size()) {
            ret = min(ret, abs(arr1[i] - arr2[j]));
            if (arr1[i] < arr2[j]) i++;
            else j++;
        }
        return ret;
    }
};

int main() {
    vector<string> v = {"practice", "makes", "perfect", "skill", "makes"};
    WordDistance ob(v);
    cout << ob.shortest("skill", "practice") << endl;
    cout << ob.shortest("makes", "skill");
}

入力と出力

入力：

{"practice", "makes", "perfect", "skill", "makes"}
Call shortest("skill", "practice")
Call shortest("makes", "skill")

出力：

3
1

出力の解説

最初の呼び出しでは、"skill" はインデックス 3 に、"practice" はインデックス 0 に出現しているため、距離は |3 − 0| = 3 です。

2番目の呼び出しでは、"makes" はインデックス 1 と 4 に、"skill" はインデックス 3 に出現しています。候補となる距離は |1 − 3| = 2 と |4 − 3| = 1 の2つなので、最短距離は 1 となります。

計算量

• コンストラクタ（前処理）：O(n) ― n は単語リストの長さです。
• shortest()：O(k1 + k2) ― k1、k2 はそれぞれ word1 と word2 の出現回数です。リスト全体を走査する必要がないため、メソッドの繰り返し呼び出しにも耐える高速な設計になっています。

まとめ

本記事では、C++で単語リスト内の2単語間の最短距離を効率的に求める方法を紹介しました。ハッシュマップによる事前の位置記録と、ソート済み配列に対する2ポインタ法を組み合わせることで、何度呼び出されても高速に応答できる実装を実現できます。同じ発想は類似の検索・照会系の問題にも応用できるので、ぜひ覚えておきましょう。