Pythonでテキスト内の2つの単語間の最小距離を求める方法

プログラミングの問題としてよく知られているのが、「テキスト中に現れる2つの指定単語の間の最小距離を求める」という課題です。
具体的には、文字列 word0、word1 および長いテキスト text が与えられたとき、テキスト内に出現する word0 と word1 の任意のペアについて、その間にある単語数として測られる距離の最小値を求めます。どちらか一方でもテキストに存在しない場合は -1 を返します。

問題の例

たとえば、次のような入力を考えてみましょう。

• text = "cat dog abcd dog cat cat abcd dog wxyz"
• word0 = "abcd"
• word1 = "wxyz"

この場合、出力は 1 になります。「abcd」と「wxyz」の間には「dog」という1つの単語しか存在しないためです。

解法のアプローチ

この問題は、テキストを単語ごとに分割し、両端から走査する「二ポインタ」的な手法で効率的に解けます。手順は以下のとおりです。

• テキストを空白で区切り、単語リスト word_list を作成する。
• 答え ans の初期値を、単語リストの長さ(最大値)とする。
• 左側のポインタ L を null(未設定)で初期化する。
• 右側のポインタ R を 0 から 単語リストの末尾まで順に動かし、以下を繰り返す。
  • word_list[R] が word0 または word1 である場合:
    • L が設定済みで、かつ word_list[R] が word_list[L] と異なる単語(つまり word0 と word1 のペア)なら、ans を「R − L − 1」と比較して小さい方に更新する。
    • その後、L を R に更新する。
• 最後に、ans が初期値(リスト全体のサイズ)のままであれば -1 を返し、そうでなければ ans を返す。

このアルゴリズムの計算量は O(n)(n は単語数)であり、非常に効率的です。

実装例(Python)

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

class Solution:
    def solve(self, text, word0, word1):
        word_list = text.split()
        ans = len(word_list)
        L = None
        for R in range(len(word_list)):
            if word_list[R] == word0 or word_list[R] == word1:
                if L is not None and word_list[R] != word_list[L]:
                    ans = min(ans, R - L - 1)
                L = R
        return -1 if ans == len(word_list) else ans

ob = Solution()
text = "cat dog abcd dog cat cat abcd dog wxyz"
word0 = "abcd"
word1 = "wxyz"
print(ob.solve(text, word0, word1))

入力

"cat dog abcd dog cat cat abcd dog wxyz", "abcd", "wxyz"

出力

1

まとめ

この手法のポイントは、直前に対象単語が出現した位置だけを記憶しておくことです。これにより、全ペアを総当たりで調べる O(n²) のアプローチを避け、線形時間 O(n) で最小距離を求められます。テキスト処理や検索機能の実装など、実務でも応用範囲の広いテクニックなので、ぜひ理解しておきましょう。