尧图网站建设 
教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇基于「算法通关手册」AlgoNote的 0243. 最短单词距离 题解 展开讲解如何在一趟遍历内用双指针计算字符串数组中两个单词的最短下标距离并延伸到 0244、0245 两个姊妹题。读完你将掌握「两个单调序列取最小差值」这一双指针套路并能直接套用到面试中的相似场景。题目理解与约束给定一个字符串数组wordsDict以及两个保证存在于数组中且互不相同的字符串word1和word2要求返回这两个单词在数组中出现位置之间的最短距离下标差的绝对值。题目关键约束如下1 ≤ wordsDict.length ≤ 3 × 10⁴数组最长 3 万个元素要求算法至少达到 $O(n)$ 级别1 ≤ wordsDict[i].length ≤ 10单词较短比较成本很低wordsDict[i]由小写英文字母组成word1与word2都在wordsDict中且word1 ≠ word2。两个官方示例来自原题解文档输入: wordsDict [practice, makes, perfect, coding, makes], word1 coding, word2 practice 输出: 3输入: wordsDict [practice, makes, perfect, coding, makes], word1 makes, word2 coding 输出: 1makes出现在下标 1 和 4coding 出现在下标 3最近的一对是下标 1 与 3距离为 2而下标 4 与 3 相邻因此最短距离为 1。注意题目要求的是任意两次出现之间的最短距离而非固定某一次出现的距离。思路分析从暴力到单次遍历最直观的暴力解法是先收集word1的所有出现位置集合 $A$、word2的所有出现位置集合 $B$再对二者做双重循环计算 $\min|a-b|$。设两个单词出现次数分别为 $m$、$n$暴力复杂度为 $O(m \times n)$在最坏情况例如数组恰好只有两种单词交替出现下退化为 $O(n^2)$无法满足 $3 \times 10^4$ 的数据规模。由于位置集合天然是递增有序的任意相邻遍历到的位置之间距离具有单调性因此可以只用一个滑动中的最近位置对来维护答案这正是本仓库 数组双指针章节 中所总结的核心思想利用序列的单调性用双指针把暴力解的 $O(n^2)$ 优化到 $O(n)$。双指针解法一趟遍历维护最近位置算法步骤初始化两个指针index1 -1、index2 -1-1表示对应单词尚未出现过初始化最小距离min_distance len(wordsDict)用数组长度作为初始上界保证第一次遇到有效对时必然能更新从左到右遍历数组若当前位置单词等于word1把index1更新为当前位置i否则若当前位置单词等于word2把index2更新为当前位置i若两个指针都已有效都不等于-1计算abs(index1 - index2)并更新min_distance遍历结束后返回min_distance。关键点在于两个指针始终保存的是各自单词最近一次出现的位置。由于指针只会不断右移、不会回退而最新的一对位置之间的差必然是当前已知最小差的候选——任何更早的位置对都已经在之前的迭代中被计算过了因此一趟遍历即可收敛到全局最优。完整可运行代码以下代码完整保留自 0243. 最短单词距离 题解并补充了typing导入使其可直接运行from typing import List class Solution: def shortestDistance(self, wordsDict: List[str], word1: str, word2: str) - int: # 初始化两个指针-1 表示还未找到对应的单词 index1, index2 -1, -1 # 初始化最小距离为数组长度 min_distance len(wordsDict) # 遍历数组 for i in range(len(wordsDict)): # 如果当前单词是 word1更新 index1 if wordsDict[i] word1: index1 i # 如果当前单词是 word2更新 index2 elif wordsDict[i] word2: index2 i # 如果两个单词都找到了计算距离并更新最小值 if index1 ! -1 and index2 ! -1: min_distance min(min_distance, abs(index1 - index2)) return min_distance代码逐行拆解index1, index2 -1, -1哨兵值设计。-1作为无效位置避免在只找到其中一个单词时就误算距离又因为数组下标从 0 开始-1不会与任何真实位置冲突。min_distance len(wordsDict)初始化为数组长度保证首个有效位置对最坏距离也不会超过数组长度减 1一定能更新它。也可以改用float(inf)语义相同。elif分支因为题目保证word1 ≠ word2同一位置不可能同时等于两个单词用if / elif结构可确保每个位置至多更新一个指针。距离更新放在循环体末尾无论本轮更新的是哪个指针只要两个指针都有效就立即尝试更新最小距离从而保证每出现一个新位置就与另一个单词最近的已知位置配对比较一次。示例推演以示例 2wordsDict [practice, makes, perfect, coding, makes]word1 makes、word2 coding为例iwordsDict[i]动作index1index2min_distance0practice无匹配-1-151makesindex1 11-152perfect无匹配1-153codingindex2 313min(5, 2) 24makesindex1 443min(2, 1) 1最终返回 1与题目输出一致。可见第二次出现makes时会立刻与coding的最近位置 3 配对捕捉到相邻下标带来的最优解。正确性要点这个解法的正确性依赖一个关键观察对任意两个单词它们各自出现位置按下标升序排列最短距离一定出现在相邻相遇的位置对上。更严格地说若 $a_1 a_2$ 是word1的连续两次出现$b$ 是word2的某次出现那么 $|a_2 - b|$ 一定不会比 $|a_1 - b|$ 更差的情况只发生在 $a_1$、$a_2$ 都在 $b$ 的同侧时——此时更靠近 $b$ 的那个即 $a_2$ 或 $a_1$ 中较近者依然会被算法保留并参与后续比较。算法始终保留最近出现位置这一策略等价于枚举了两单词出现序列之间的所有相邻候选对从而不漏掉全局最小。从源码结构看这种记录最近一次命中位置的双指针写法与仓库中 数组双指针章节 总结的快慢指针/分离双指针模板同源——它利用的正是序列的单调性来避免回溯属于双指针三大范式对撞、快慢、分离中同向推进、维护区间最优的变体。复杂度分析时间复杂度$O(n)$其中 $n$ 是数组wordsDict的长度。全程只遍历数组一次每个元素至多触发一次指针更新和一次距离比较空间复杂度$O(1)$仅使用index1、index2、min_distance三个常数级变量无需哈希表或额外数组。相比暴力枚举 $O(m \times n)$ 的最坏情况双指针把时间成本压到与数组长度线性相关在3 × 10⁴的规模下是确定可行的。姊妹题延伸同一思路的三种变体「最短单词距离」在 LeetCode 上共有三道连续编号的题目仓库均配有完整题解可作为本讲的延伸练习0243. 最短单词距离本题单次查询双指针单趟遍历0244. 最短单词距离 II中等要求设计WordDistance类构造时接收数组、shortest(word1, word2)会被多次调用。解法转为哈希表存位置列表 分离双指针归并构造时用哈希表记录每个单词的所有出现下标$O(n)$查询时对两个递增位置列表做双指针归并比较每次查询 $O(mn)$。这展示了查询频次决定预处理策略的工程权衡0245. 最短单词距离 III中等放宽约束允许word1 word2此时要找的是同一个单词两次不同出现间的最短距离。解法在双指针基础上增加特判遇到该单词时先把旧index1迁移到index2再更新index1并额外要求index1 ! index2才计算距离。三个题目难度递增正好覆盖了单次查询、多次查询、单词相同的边界三类常见考法建议按顺序刷完以形成完整认知。在本仓库中的学习路径本仓库算法通关手册 / AlgoNote将本题收录于 200 道高频面试题之列对应的学习资源包括基础理论数组双指针章节系统讲解对撞指针、快慢指针、分离双指针三类范式与通用模板本章题解索引0200-0299 题解目录可对照 0243/0244/0245 三连题分类刷题列表LeetCode 分类题解清单可按「数组」「双指针」等标签检索更多同类练习例如 0015 三数之和、0088 合并两个有序数组、0283 移动零等完整题解总表LeetCode 题解列表。建议的练习顺序是先独立实现一遍本题再尝试将解法改写为预先收集两个位置列表后用双指针归并的等价形式最后把 0245 的相同单词边界亲手调通即可牢固掌握这一面试高频套路。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐x64dbg AddArg 命令详解为函数类型逐个追加参数的完整指南x64dbg AddArg 命令详解为函数类型逐个追加参数的完整指南 AddArg 是 x64dbg 类型系统命令族中的一员用于向已存在的函数类型末尾追加一教程文档知识库leetcode 题解821. 字符的最短距离双向遍历解法全解析leetcode 题解821. 字符的最短距离双向遍历解法全解析 本篇技术指南基于本仓库题解 problems/821.shortest distance文档教程知识库AlgoNote 题解 | 0272. 最接近的二叉搜索树值 IIBST 中序遍历 距离排序求解 Top-K 最近值AlgoNote 题解 | 0272. 最接近的二叉搜索树值 IIBST 中序遍历 距离排序求解 Top K 最近值 导读 本篇是 AlgoNote「算法教程文档知识库上一篇MySQL触发器应用实战自动化数据处理的最佳实践下一篇GPT-Newspaper安全最佳实践保护你的个性化新闻数据创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 0243 最短单词距离（AlgoNote 双指针题解）：单次遍历求数组中两单词最近距离
教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇基于「算法通关手册」AlgoNote的 0243. 最短单词距离 题解 展开讲解如何在一趟遍历内用双指针计算字符串数组中两个单词的最短下标距离并延伸到 0244、0245 两个姊妹题。读完你将掌握「两个单调序列取最小差值」这一双指针套路并能直接套用到面试中的相似场景。题目理解与约束给定一个字符串数组wordsDict以及两个保证存在于数组中且互不相同的字符串word1和word2要求返回这两个单词在数组中出现位置之间的最短距离下标差的绝对值。题目关键约束如下1 ≤ wordsDict.length ≤ 3 × 10⁴数组最长 3 万个元素要求算法至少达到 $O(n)$ 级别1 ≤ wordsDict[i].length ≤ 10单词较短比较成本很低wordsDict[i]由小写英文字母组成word1与word2都在wordsDict中且word1 ≠ word2。两个官方示例来自原题解文档输入: wordsDict [practice, makes, perfect, coding, makes], word1 coding, word2 practice 输出: 3输入: wordsDict [practice, makes, perfect, coding, makes], word1 makes, word2 coding 输出: 1makes出现在下标 1 和 4coding 出现在下标 3最近的一对是下标 1 与 3距离为 2而下标 4 与 3 相邻因此最短距离为 1。注意题目要求的是任意两次出现之间的最短距离而非固定某一次出现的距离。思路分析从暴力到单次遍历最直观的暴力解法是先收集word1的所有出现位置集合 $A$、word2的所有出现位置集合 $B$再对二者做双重循环计算 $\min|a-b|$。设两个单词出现次数分别为 $m$、$n$暴力复杂度为 $O(m \times n)$在最坏情况例如数组恰好只有两种单词交替出现下退化为 $O(n^2)$无法满足 $3 \times 10^4$ 的数据规模。由于位置集合天然是递增有序的任意相邻遍历到的位置之间距离具有单调性因此可以只用一个滑动中的最近位置对来维护答案这正是本仓库 数组双指针章节 中所总结的核心思想利用序列的单调性用双指针把暴力解的 $O(n^2)$ 优化到 $O(n)$。双指针解法一趟遍历维护最近位置算法步骤初始化两个指针index1 -1、index2 -1-1表示对应单词尚未出现过初始化最小距离min_distance len(wordsDict)用数组长度作为初始上界保证第一次遇到有效对时必然能更新从左到右遍历数组若当前位置单词等于word1把index1更新为当前位置i否则若当前位置单词等于word2把index2更新为当前位置i若两个指针都已有效都不等于-1计算abs(index1 - index2)并更新min_distance遍历结束后返回min_distance。关键点在于两个指针始终保存的是各自单词最近一次出现的位置。由于指针只会不断右移、不会回退而最新的一对位置之间的差必然是当前已知最小差的候选——任何更早的位置对都已经在之前的迭代中被计算过了因此一趟遍历即可收敛到全局最优。完整可运行代码以下代码完整保留自 0243. 最短单词距离 题解并补充了typing导入使其可直接运行from typing import List class Solution: def shortestDistance(self, wordsDict: List[str], word1: str, word2: str) - int: # 初始化两个指针-1 表示还未找到对应的单词 index1, index2 -1, -1 # 初始化最小距离为数组长度 min_distance len(wordsDict) # 遍历数组 for i in range(len(wordsDict)): # 如果当前单词是 word1更新 index1 if wordsDict[i] word1: index1 i # 如果当前单词是 word2更新 index2 elif wordsDict[i] word2: index2 i # 如果两个单词都找到了计算距离并更新最小值 if index1 ! -1 and index2 ! -1: min_distance min(min_distance, abs(index1 - index2)) return min_distance代码逐行拆解index1, index2 -1, -1哨兵值设计。-1作为无效位置避免在只找到其中一个单词时就误算距离又因为数组下标从 0 开始-1不会与任何真实位置冲突。min_distance len(wordsDict)初始化为数组长度保证首个有效位置对最坏距离也不会超过数组长度减 1一定能更新它。也可以改用float(inf)语义相同。elif分支因为题目保证word1 ≠ word2同一位置不可能同时等于两个单词用if / elif结构可确保每个位置至多更新一个指针。距离更新放在循环体末尾无论本轮更新的是哪个指针只要两个指针都有效就立即尝试更新最小距离从而保证每出现一个新位置就与另一个单词最近的已知位置配对比较一次。示例推演以示例 2wordsDict [practice, makes, perfect, coding, makes]word1 makes、word2 coding为例iwordsDict[i]动作index1index2min_distance0practice无匹配-1-151makesindex1 11-152perfect无匹配1-153codingindex2 313min(5, 2) 24makesindex1 443min(2, 1) 1最终返回 1与题目输出一致。可见第二次出现makes时会立刻与coding的最近位置 3 配对捕捉到相邻下标带来的最优解。正确性要点这个解法的正确性依赖一个关键观察对任意两个单词它们各自出现位置按下标升序排列最短距离一定出现在相邻相遇的位置对上。更严格地说若 $a_1 a_2$ 是word1的连续两次出现$b$ 是word2的某次出现那么 $|a_2 - b|$ 一定不会比 $|a_1 - b|$ 更差的情况只发生在 $a_1$、$a_2$ 都在 $b$ 的同侧时——此时更靠近 $b$ 的那个即 $a_2$ 或 $a_1$ 中较近者依然会被算法保留并参与后续比较。算法始终保留最近出现位置这一策略等价于枚举了两单词出现序列之间的所有相邻候选对从而不漏掉全局最小。从源码结构看这种记录最近一次命中位置的双指针写法与仓库中 数组双指针章节 总结的快慢指针/分离双指针模板同源——它利用的正是序列的单调性来避免回溯属于双指针三大范式对撞、快慢、分离中同向推进、维护区间最优的变体。复杂度分析时间复杂度$O(n)$其中 $n$ 是数组wordsDict的长度。全程只遍历数组一次每个元素至多触发一次指针更新和一次距离比较空间复杂度$O(1)$仅使用index1、index2、min_distance三个常数级变量无需哈希表或额外数组。相比暴力枚举 $O(m \times n)$ 的最坏情况双指针把时间成本压到与数组长度线性相关在3 × 10⁴的规模下是确定可行的。姊妹题延伸同一思路的三种变体「最短单词距离」在 LeetCode 上共有三道连续编号的题目仓库均配有完整题解可作为本讲的延伸练习0243. 最短单词距离本题单次查询双指针单趟遍历0244. 最短单词距离 II中等要求设计WordDistance类构造时接收数组、shortest(word1, word2)会被多次调用。解法转为哈希表存位置列表 分离双指针归并构造时用哈希表记录每个单词的所有出现下标$O(n)$查询时对两个递增位置列表做双指针归并比较每次查询 $O(mn)$。这展示了查询频次决定预处理策略的工程权衡0245. 最短单词距离 III中等放宽约束允许word1 word2此时要找的是同一个单词两次不同出现间的最短距离。解法在双指针基础上增加特判遇到该单词时先把旧index1迁移到index2再更新index1并额外要求index1 ! index2才计算距离。三个题目难度递增正好覆盖了单次查询、多次查询、单词相同的边界三类常见考法建议按顺序刷完以形成完整认知。在本仓库中的学习路径本仓库算法通关手册 / AlgoNote将本题收录于 200 道高频面试题之列对应的学习资源包括基础理论数组双指针章节系统讲解对撞指针、快慢指针、分离双指针三类范式与通用模板本章题解索引0200-0299 题解目录可对照 0243/0244/0245 三连题分类刷题列表LeetCode 分类题解清单可按「数组」「双指针」等标签检索更多同类练习例如 0015 三数之和、0088 合并两个有序数组、0283 移动零等完整题解总表LeetCode 题解列表。建议的练习顺序是先独立实现一遍本题再尝试将解法改写为预先收集两个位置列表后用双指针归并的等价形式最后把 0245 的相同单词边界亲手调通即可牢固掌握这一面试高频套路。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐x64dbg AddArg 命令详解为函数类型逐个追加参数的完整指南x64dbg AddArg 命令详解为函数类型逐个追加参数的完整指南 AddArg 是 x64dbg 类型系统命令族中的一员用于向已存在的函数类型末尾追加一教程文档知识库leetcode 题解821. 字符的最短距离双向遍历解法全解析leetcode 题解821. 字符的最短距离双向遍历解法全解析 本篇技术指南基于本仓库题解 problems/821.shortest distance文档教程知识库AlgoNote 题解 | 0272. 最接近的二叉搜索树值 IIBST 中序遍历 距离排序求解 Top-K 最近值AlgoNote 题解 | 0272. 最接近的二叉搜索树值 IIBST 中序遍历 距离排序求解 Top K 最近值 导读 本篇是 AlgoNote「算法教程文档知识库上一篇MySQL触发器应用实战自动化数据处理的最佳实践下一篇GPT-Newspaper安全最佳实践保护你的个性化新闻数据创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考