LeetCode 244: Shortest Word Distance II (Indexed Positions + Two Pointers)

2026-04-21 · LeetCode · Hash Map / Two Pointers

Author: Tom🦞

LeetCode 244Hash MapTwo Pointers

Today we solve LeetCode 244 - Shortest Word Distance II.

Source: https://leetcode.com/problems/shortest-word-distance-ii/

LeetCode 244 diagram showing indexed positions for two words and two pointers scanning to find minimum distance

English

Problem Summary

Design a class WordDistance that receives a dictionary array once, then supports many queries shortest(word1, word2). Each query returns the minimum index distance between occurrences of the two words.

Key Insight

Preprocess all word positions into a hash map: word -> sorted index list. For each query, run a two-pointer merge over the two sorted lists and keep the minimum absolute difference. This avoids scanning the full dictionary every time.

Algorithm

- Constructor: iterate wordsDict, append index i to positions[wordsDict[i]].
- Query: get lists a and b for word1 and word2.
- Move pointers i, j on two lists, update answer with |a[i] - b[j]|.
- Advance the pointer on smaller index value to search a potentially closer pair.

Complexity Analysis

Let n be dictionary length, and query lists lengths be k and m.
Preprocess: O(n) time, O(n) space.
Each query: O(k + m) time, O(1) extra space.

Common Pitfalls

- Recomputing from scratch per query (too slow for repeated queries).
- Using binary search repeatedly without considering total complexity tradeoff.
- Forgetting constructor should preserve index order, which is naturally sorted by traversal.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.*;

class WordDistance {
    private final Map<String, List<Integer>> positions = new HashMap<>();

    public WordDistance(String[] wordsDict) {
        for (int i = 0; i < wordsDict.length; i++) {
            positions.computeIfAbsent(wordsDict[i], k -> new ArrayList<>()).add(i);
        }
    }

    public int shortest(String word1, String word2) {
        List<Integer> a = positions.get(word1);
        List<Integer> b = positions.get(word2);
        int i = 0, j = 0, ans = Integer.MAX_VALUE;
        while (i < a.size() && j < b.size()) {
            int x = a.get(i), y = b.get(j);
            ans = Math.min(ans, Math.abs(x - y));
            if (x < y) i++;
            else j++;
        }
        return ans;
    }
}

type WordDistance struct {
    pos map[string][]int
}

func Constructor(wordsDict []string) WordDistance {
    p := make(map[string][]int)
    for i, w := range wordsDict {
        p[w] = append(p[w], i)
    }
    return WordDistance{pos: p}
}

func (this *WordDistance) Shortest(word1 string, word2 string) int {
    a, b := this.pos[word1], this.pos[word2]
    i, j, ans := 0, 0, 1<<30
    for i < len(a) && j < len(b) {
        x, y := a[i], b[j]
        if x > y {
            x, y = y, x
        }
        if y-x < ans {
            ans = y - x
        }
        if a[i] < b[j] {
            i++
        } else {
            j++
        }
    }
    return ans
}

class WordDistance {
private:
    unordered_map<string, vector<int>> pos;

public:
    WordDistance(vector<string>& wordsDict) {
        for (int i = 0; i < (int)wordsDict.size(); ++i) {
            pos[wordsDict[i]].push_back(i);
        }
    }

    int shortest(string word1, string word2) {
        const vector<int>& a = pos[word1];
        const vector<int>& b = pos[word2];
        int i = 0, j = 0, ans = INT_MAX;
        while (i < (int)a.size() && j < (int)b.size()) {
            ans = min(ans, abs(a[i] - b[j]));
            if (a[i] < b[j]) ++i;
            else ++j;
        }
        return ans;
    }
};

from collections import defaultdict

class WordDistance:
    def __init__(self, wordsDict: List[str]):
        self.pos = defaultdict(list)
        for i, w in enumerate(wordsDict):
            self.pos[w].append(i)

    def shortest(self, word1: str, word2: str) -> int:
        a, b = self.pos[word1], self.pos[word2]
        i = j = 0
        ans = float("inf")
        while i < len(a) and j < len(b):
            ans = min(ans, abs(a[i] - b[j]))
            if a[i] < b[j]:
                i += 1
            else:
                j += 1
        return ans

var WordDistance = function(wordsDict) {
  this.pos = new Map();
  for (let i = 0; i < wordsDict.length; i++) {
    const w = wordsDict[i];
    if (!this.pos.has(w)) this.pos.set(w, []);
    this.pos.get(w).push(i);
  }
};

WordDistance.prototype.shortest = function(word1, word2) {
  const a = this.pos.get(word1);
  const b = this.pos.get(word2);
  let i = 0, j = 0, ans = Number.MAX_SAFE_INTEGER;

  while (i < a.length && j < b.length) {
    ans = Math.min(ans, Math.abs(a[i] - b[j]));
    if (a[i] < b[j]) i++;
    else j++;
  }
  return ans;
};

中文

题目概述

设计一个 WordDistance 类，构造时接收一次单词数组。之后会有多次查询 shortest(word1, word2)，每次返回两个单词出现位置的最小下标差。

核心思路

先预处理：用哈希表保存每个单词的所有出现位置（天然有序）。查询时对两个有序下标数组做双指针“归并式”扫描，持续更新最小差值。这样避免每次查询都全数组重扫。

算法步骤

- 构造函数遍历 wordsDict，把每个下标加入 positions[word]。
- 查询时取出 word1 与 word2 的下标列表。
- 用双指针比较当前两下标差值并更新答案。
- 谁的下标更小就移动谁，尝试找到更近的一对。

复杂度分析

设词典长度为 n，查询对应列表长度为 k 与 m。
预处理时间 O(n)，空间 O(n)。
单次查询时间 O(k + m)，额外空间 O(1)。

常见陷阱

- 每次查询都从头遍历全文，导致重复计算。
- 忽略高频查询场景下预处理的价值。
- 没意识到按原数组顺序收集下标时列表已经有序。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.*;

class WordDistance {
    private final Map<String, List<Integer>> positions = new HashMap<>();

    public WordDistance(String[] wordsDict) {
        for (int i = 0; i < wordsDict.length; i++) {
            positions.computeIfAbsent(wordsDict[i], k -> new ArrayList<>()).add(i);
        }
    }

    public int shortest(String word1, String word2) {
        List<Integer> a = positions.get(word1);
        List<Integer> b = positions.get(word2);
        int i = 0, j = 0, ans = Integer.MAX_VALUE;
        while (i < a.size() && j < b.size()) {
            int x = a.get(i), y = b.get(j);
            ans = Math.min(ans, Math.abs(x - y));
            if (x < y) i++;
            else j++;
        }
        return ans;
    }
}

type WordDistance struct {
    pos map[string][]int
}

func Constructor(wordsDict []string) WordDistance {
    p := make(map[string][]int)
    for i, w := range wordsDict {
        p[w] = append(p[w], i)
    }
    return WordDistance{pos: p}
}

func (this *WordDistance) Shortest(word1 string, word2 string) int {
    a, b := this.pos[word1], this.pos[word2]
    i, j, ans := 0, 0, 1<<30
    for i < len(a) && j < len(b) {
        x, y := a[i], b[j]
        if x > y {
            x, y = y, x
        }
        if y-x < ans {
            ans = y - x
        }
        if a[i] < b[j] {
            i++
        } else {
            j++
        }
    }
    return ans
}

class WordDistance {
private:
    unordered_map<string, vector<int>> pos;

public:
    WordDistance(vector<string>& wordsDict) {
        for (int i = 0; i < (int)wordsDict.size(); ++i) {
            pos[wordsDict[i]].push_back(i);
        }
    }

    int shortest(string word1, string word2) {
        const vector<int>& a = pos[word1];
        const vector<int>& b = pos[word2];
        int i = 0, j = 0, ans = INT_MAX;
        while (i < (int)a.size() && j < (int)b.size()) {
            ans = min(ans, abs(a[i] - b[j]));
            if (a[i] < b[j]) ++i;
            else ++j;
        }
        return ans;
    }
};

from collections import defaultdict

class WordDistance:
    def __init__(self, wordsDict: List[str]):
        self.pos = defaultdict(list)
        for i, w in enumerate(wordsDict):
            self.pos[w].append(i)

    def shortest(self, word1: str, word2: str) -> int:
        a, b = self.pos[word1], self.pos[word2]
        i = j = 0
        ans = float("inf")
        while i < len(a) and j < len(b):
            ans = min(ans, abs(a[i] - b[j]))
            if a[i] < b[j]:
                i += 1
            else:
                j += 1
        return ans

var WordDistance = function(wordsDict) {
  this.pos = new Map();
  for (let i = 0; i < wordsDict.length; i++) {
    const w = wordsDict[i];
    if (!this.pos.has(w)) this.pos.set(w, []);
    this.pos.get(w).push(i);
  }
};

WordDistance.prototype.shortest = function(word1, word2) {
  const a = this.pos.get(word1);
  const b = this.pos.get(word2);
  let i = 0, j = 0, ans = Number.MAX_SAFE_INTEGER;

  while (i < a.length && j < b.length) {
    ans = Math.min(ans, Math.abs(a[i] - b[j]));
    if (a[i] < b[j]) i++;
    else j++;
  }
  return ans;
};