LeetCode 243. 最短单词距离

2026-09-13 HGNULB 约 4 分钟

文章信息 2 个分类 2 个标签

分类

LeetCode 简单

题目描述

✅ 243. 最短单词距离

题意分析

给定单词数组和两个不同的目标词，求它们任意两次出现位置之间的最小下标差。目标词都保证在数组中出现，但同一个词可能出现多次，所以只找第一次出现的位置并不够。

如果枚举两个词的全部出现位置配对，就会重复比较许多更远的位置。这里只查询一次最小距离，可以从左到右扫描，用两个变量保存目标词最近一次出现的位置，不必建立完整位置列表。

解法：记录两个目标词的最近位置

核心思路

[!blue]

first、second 分别表示截至当前位置，word1、word2 最近出现的下标，初始设为 -1，表示尚未见到。best 保存已经检查过的配对中最小的距离，初值设为数组长度，严格大于任何合法距离。

假设当前下标 i 出现 word1。对任何已经出现的 word2 下标 j，距离都是 i-j；j 越大，距离越小，因此只需与最近的 second 配对，早先出现的位置不可能更好。遇到 word2 时同理。

为什么不会漏掉最优配对？任意一对位置都有一个较晚的端点。当扫描到这个端点时，另一种词最近的位置至少不会比该配对中的较早端点更远，所以当前算出的候选距离不大于这对位置的距离。于是全局最小值一定能够被记录。

每轮先更新当前词对应的位置，再在两个位置均非负时更新 best。代码在非目标词处也执行这个检查，此时两个位置都未改变，只是重复比较原候选，不影响结果。

解题步骤

初始化 first = -1、second = -1、best = wordsDict.length。

从左到右扫描数组，遇到 word1 就更新 first，遇到 word2 就更新 second。

两个目标词都已出现时，用 abs(first-second) 更新最小值。Java 直接调用绝对值函数，Go 代码通过负数取反得到同样的距离。

扫描结束返回 best。题目保证两个目标词存在，所以初始值一定会被合法距离替换。

对 ["a","x","b","a"] 查询 a、b：扫描到下标 2 时，最近位置为 0、2，得到距离 2；扫描到下标 3 时，把 a 的位置更新为 3，得到距离 1。因此必须持续更新最近位置，而不能停留在第一次出现。

代码实现

class Solution {
    public int shortestDistance(String[] wordsDict, String word1, String word2) {
        int first = -1;
        int second = -1;
        int best = wordsDict.length;

        for (int i = 0; i < wordsDict.length; i++) {
            if (wordsDict[i].equals(word1)) {
                first = i;
            }

            if (wordsDict[i].equals(word2)) {
                second = i;
            }

            if (first >= 0 && second >= 0) {
                best = Math.min(best, Math.abs(first - second));
            }
        }

        return best;
    }
}

func shortestDistance(wordsDict []string, word1, word2 string) int {
    first, second, best := -1, -1, len(wordsDict)
    for i, word := range wordsDict {
        if word == word1 {
            first = i
        }
        if word == word2 {
            second = i
        }
        if first >= 0 && second >= 0 {
            distance := first - second
            if distance < 0 {
                distance = -distance
            }
            best = min(best, distance)
        }
    }
    return best
}

复杂度分析

时间复杂度：若把一次单词比较看作常数，扫描需要 $O(n)$ 时间。计入字符串比较成本时，上界为 $O(nL)$，其中 $L$ 是最长单词长度。

空间复杂度：$O(1)$，只保存两个位置、当前距离与最优距离，不建立出现位置列表。

关键点总结

[!green]

扫描方向使当前位置右侧尚不可用，而左侧距离最近的候选一定是最近一次出现。

较早位置被较新位置替代后，未来也不会重新变得更优，因此可以直接覆盖。

更新答案前必须确认两个目标词都已经出现，-1 不能参与合法距离计算。

两个目标词不同，所以一个数组位置不会同时成为同一对的两个端点。

易错点总结

[!yellow]

只记录第一次出现位置：后面出现的目标词可能形成更短距离。

把初始位置设为 0：会把尚未出现的词误当成在数组开头出现，必须使用无效下标 -1。

忘记取绝对值：两个目标词谁在前面都可能发生，距离不能为负数。

只在遇到某一种目标词时更新答案：最优配对的较晚端点可能是另一种词，应在两种位置更新后都考虑候选。

允许两个目标词相同却沿用本实现：同一位置会同时更新两个下标，产生错误的 0；本题明确保证目标词不同。

相似题目

题目	难度	关联与区别
244. 最短单词距离 II	中等	同一词表改为多次查询，预先保存各词的位置列表，再用双指针求最近距离。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/97690393

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！