C++で解く「最短単語距離 III」— 効率的なアルゴリズムと実装例を解説

単語のリストと、word1・word2 という2つの単語が与えられたとき、リスト内におけるこれら2つの単語間の最短距離を求めるのが本問題です。注意点として、word1 と word2 が同じ単語であるケースも存在します。例として、words = ["practice", "makes", "perfect", "skill", "makes"] というリストを考えてみましょう。

このとき、入力が word1 = "makes"、word2 = "skill" であれば、出力は 1 となります。

解法のアプローチ

この問題は、リストを先頭から一度走査しながら、各単語の最新の出現位置を記録していくことで、線形時間で効率よく解くことができます。具体的な手順は以下の通りです。

• ret := 10^9、l1 := 10^9、l2 := -10^9 で初期化します。

• n := words のサイズとします。

• i := 0 から i < n の間、i を1ずつ増やしながら以下を繰り返します。

  • words[i] が word1 と一致する場合 → l1 := i と更新します。

  • words[i] が word2 と一致する場合 → word1 と word2 が同一であれば、まず l1 := l2 としたうえで、l2 := i と更新します。

  • ret := min(|l2 − l1|, ret) として、これまでの最小距離を更新します。

• ループ終了後、ret を返します。

word1 と word2 が同じ場合に l1 := l2 を代入しているのは、直前の出現位置を保持するためです。これにより、同一単語同士の距離も正しく計算できるようになります。

C++ 実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int shortestWordDistance(vector<string>& words, string word1, string word2) {
      int ret = 1e9;
      int l1 = 1e9;
      int l2 = -1e9;
      int n = words.size();
      for (int i = 0; i < n; i++) {
         if (words[i] == word1) {
            l1 = i;
         }
         if (words[i] == word2) {
            if (word1 == word2) {
               l1 = l2;
            }
            l2 = i;
         }
         ret = min(abs(l2 - l1), ret);
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<string> v = {"practice", "makes", "perfect", "skill", "makes"};
   cout << (ob.shortestWordDistance(v, "makes", "skill"));
}

入力

{"practice", "makes", "perfect", "skill", "makes"}, "makes", "skill"

出力

1

計算量

• 時間計算量：O(n) — リスト全体を一度だけ走査します。

• 空間計算量：O(1) — 定数個の変数のみを使用します。