教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载导读本文基于「宫水三叶的刷题日记」刷穿 LeetCode 系列的第 821 篇题解对应仓库文档 LeetCode/821-830/821. 字符的最短距离简单.md完整解析一道难度为「简单」的字符串距离计算问题给定字符串s与字符c为s中每个下标计算到最近一个c字符的绝对距离。文章将继承原题解给出的「两次遍历模拟」与「多源 BFS」两种解法思路并补充 Java、C、Python、TypeScript 四种语言的完整可运行代码、边界条件推演与复杂度对比。读完本文你将掌握「分方向扫描求最近距离」这一通用模拟技巧以及把一维数组上的最近距离问题建模为「多源 BFS」的抽象方法为后续刷同类字符/数组距离题如推多米诺、蜡烛之间的盘子等打下基础。题目背景与题意分析本题为 LeetCode 第 821 题「字符的最短距离」Shortest Distance to a Character难度为简单原题解中标注的 Tag 为「模拟」「BFS」。在仓库的 Index/模拟.md 与 Index/BFS.md 两张索引表中本题均被收录且推荐指数为 属于值得反复练习的入门级双解法例题。题目描述如下给你一个字符串s和一个字符c且c是s中出现过的字符。返回一个整数数组answer其中answer.length s.length且answer[i]是s中从下标i到离它最近的字符c的距离。两个下标i和j之间的距离为abs(i - j)其中abs是绝对值函数。示例推演示例 1输入s loveleetcode, c e 输出[3,2,1,0,1,0,0,1,2,2,1,0]字符e出现在下标 3、5、6 和 11 处下标从 0 开始计数距下标 0 最近的e出现在下标 3所以距离为abs(0 - 3) 3距下标 1 最近的e出现在下标 3所以距离为abs(1 - 3) 2对于下标 4出现在下标 3 和下标 5 处的e都离它最近但距离相同abs(4 - 3) abs(4 - 5) 1距下标 8 最近的e出现在下标 6所以距离为abs(8 - 6) 2。示例 2输入s aaab, c b 输出[3,2,1,0]数据范围提示1 s.length 10^4s[i]和c均为小写英文字母题目数据保证c在s中至少出现一次。数据范围决定了两种解法均为 $O(n)$ 时间都能轻松通过而「c至少出现一次」这一保证是两种解法在实现细节上可以简化处理的依据。解法一两次遍历模拟推荐掌握核心思路根据题意直接模拟第一次从左到右遍历找到每个下标i左边最近的c第二次从右到左遍历找到每个下标i右边最近的c。两者取较小值即为该位置到最近c的距离。这里有一个关键的实现技巧用变量j记录当前方向上最近一次遇到c的下标初始化为-1表示尚未遇到。由于题目保证c至少出现一次正向遍历结束后所有位置都必然已被左边某个c覆盖反向遍历则用于修正「右边的c更近」的情况。另一个关键点是答案数组的初始值原题解将ans全部初始化为n 1一个大于任何可能距离的值因为两点间最大距离为n - 1。这样在正向遍历中尚未被任何c覆盖的位置其值n 1会在反向遍历时被右侧最近的c修正而所有位置最终都会被修正为真实距离不会残留初始值。即使不使用n 1而直接使用Integer.MAX_VALUE之类的极大值效果也相同——选择n 1是因为它足够大且计算安全。Java 实现class Solution { public int[] shortestToChar(String s, char c) { int n s.length(); int[] ans new int[n]; Arrays.fill(ans, n 1); // 第一趟从左到右找每个 i 左边最近的 c for (int i 0, j -1; i n; i) { if (s.charAt(i) c) j i; if (j ! -1) ans[i] i - j; } // 第二趟从右到左找每个 i 右边最近的 c并与左边结果取 min for (int i n - 1, j -1; i 0; i--) { if (s.charAt(i) c) j i; if (j ! -1) ans[i] Math.min(ans[i], j - i); } return ans; } }C 实现class Solution { public: vectorint shortestToChar(string s, char c) { int n s.length(); vectorint ans(n, n 1); for (int i 0, j -1; i n; i) { if (s[i] c) j i; if (j ! -1) ans[i] i - j; } for (int i n - 1, j -1; i 0; i--) { if (s[i] c) j i; if (j ! -1) ans[i] min(ans[i], j - i); } return ans; } };Python 实现class Solution: def shortestToChar(self, s: str, c: str) - List[int]: n len(s) ans [n 1] * n # 第一趟从左到右 j -1 for i in range(n): if s[i] c: j i if j ! -1: ans[i] i - j # 第二趟从右到左 j -1 for i in range(n - 1, -1, -1): if s[i] c: j i if j ! -1: ans[i] min(ans[i], j - i) return ansTypeScript 实现function shortestToChar(s: string, c: string): number[] { const n s.length; const ans new Array(n).fill(n 1); for (let i 0, j -1; i n; i) { if (s.charAt(i) c) j i; if (j ! -1) ans[i] i - j; } for (let i n - 1, j -1; i 0; i--) { if (s.charAt(i) c) j i; if (j ! -1) ans[i] Math.min(ans[i], j - i); } return ans; }边界情况推演以s aaab, c b为例正向遍历后ans [3, 2, 1, 0]下标 3 是b距离为 0其余位置记录到左边最近b的距离即3 - i反向遍历时j从下标 3 开始一直保持为 3j - i恒等于3 - i与正向结果相同min取后结果不变。再以s loveleetcode, c e为例正向遍历只能保证每个位置记录的是「到左侧最近e」的距离例如下标 7t正向得到7 - 6 1反向时最近e仍在下标 6得到6 - 7 -1的绝对值为 1min(1, 1) 1而下标 9d正向得到9 - 6 3反向时最近e在下标 11得到11 - 9 2min(3, 2) 2正好与示例输出吻合。复杂度时间复杂度$O(n)$两次线性扫描空间复杂度$O(1)$不计返回答案数组本身仅使用常数个辅助变量。解法二多源 BFS一维数组上的多起点扩散核心思路把问题转化为「从多个源点出发的最短路」问题所有出现c的下标都是源点距离为 0在一维数组上允许向左右两个方向移动一步求每个位置到最近源点的距离。这正是「多源 BFS」在数组上的直接应用。实现要点初始化ans全部为-1同时把-1作为「是否已被访问」的标记遍历一遍字符串把所有等于c的下标入队Deque并将对应ans[i]置为0定义方向数组dirs {-1, 1}代表向左右各扩散一步从队头取出下标t对每个方向计算出新下标ne t di若ne在[0, n)范围内且ans[ne] -1尚未访问则更新ans[ne] ans[t] 1并入队。由于每个下标只被访问一次以-1标记判重BFS 天然保证首次到达某位置时经过的步数就是该位置到最近源点的距离因此ans[ne] ans[t] 1即为正确答案无需再取min。Java 实现class Solution { public int[] shortestToChar(String s, char c) { int n s.length(); int[] ans new int[n]; Arrays.fill(ans, -1); DequeInteger d new ArrayDeque(); // 将所有 c 字符的下标作为源点入队距离记为 0 for (int i 0; i n; i) { if (s.charAt(i) c) { d.addLast(i); ans[i] 0; } } int[] dirs new int[]{-1, 1}; while (!d.isEmpty()) { int t d.pollFirst(); for (int di : dirs) { int ne t di; if (ne 0 ne n ans[ne] -1) { ans[ne] ans[t] 1; d.addLast(ne); } } } return ans; } }C 实现class Solution { public: vectorint shortestToChar(string s, char c) { int n s.length(); vectorint ans(n, -1); dequeint d; for (int i 0; i n; i) { if (s[i] c) { d.push_back(i); ans[i] 0; } } vectorint dirs {-1, 1}; while (!d.empty()) { int t d.front(); d.pop_front(); for (auto di : dirs) { int ne t di; if (ne 0 ne n ans[ne] -1) { ans[ne] ans[t] 1; d.push_back(ne); } } } return ans; } };Python 实现class Solution: def shortestToChar(self, s: str, c: str) - List[int]: n len(s) ans [-1] * n d deque() for i in range(n): if s[i] c: d.append(i) ans[i] 0 dirs [-1, 1] while d: t d.popleft() for di in dirs: ne t di if 0 ne n and ans[ne] -1: ans[ne] ans[t] 1 d.append(ne) return ansTypeScript 实现function shortestToChar(s: string, c: string): number[] { const n s.length; const ans new Array(n).fill(-1); const d: number[] []; for (let i 0; i n; i) { if (s.charAt(i) c) { d.push(i); ans[i] 0; } } const dirs [-1, 1]; while (d.length 0) { const t d.shift() as number; for (const di of dirs) { const ne t di; if (ne 0 ne n ans[ne] -1) { ans[ne] ans[t] 1; d.push(ne); } } } return ans; }为什么-1初始化是安全的因为题目保证c至少出现一次所有源点都已被标记为0并入队队列非空时 BFS 必然从源点逐层向外扩散最终覆盖整个数组不会出现「某个位置永远停留在-1」的死角。-1在这里同时充当「未访问」标记与「非法距离」占位是本题 BFS 写法简洁的关键。复杂度时间复杂度$O(n)$每个下标至多入队、出队一次空间复杂度$O(n)$队列在最坏情况下如所有位置都被同一批源点扩散前入队需要容纳 $O(n)$ 个下标。两种解法对比与选用建议维度两次遍历模拟多源 BFS核心思想分左右两个方向各扫描一遍取min所有c为源点向左右逐层扩散时间复杂度$O(n)$$O(n)$空间复杂度$O(1)$不计答案数组$O(n)$队列实现难度低仅需两个循环与一个j指针中需掌握队列与方向数组判重手段无需判重天然无重复计算以ans[i] -1作为访问标记可扩展性仅适用于一维「最近同类点」问题可推广到二维网格、多源最短路等场景在仓库 Index/BFS.md 收录的题目如 90. 子集 II、397. 整数替换、403. 青蛙过河、429. N 叉树的层序遍历等中BFS 通常作用于树、图或二维网格本题的特殊之处在于把 BFS 用在一维数组上方向数组只有{-1, 1}两个取值是理解「多源 BFS 判重与分层扩散」的最佳入门样例。而两次遍历模拟则属于 Index/模拟.md 所归纳的字符串模拟类题目如 38. 外观数列、58. 最后一个单词的长度、482. 密钥格式化等中的典型套路——「正反两次扫描 前缀/后缀信息合并」这一套路在「蜡烛之间的盘子」等稍复杂题目中同样适用。刷题要点小结看到「到最近某个位置的距离」先想是否可以用两次扫描分别维护「左侧最近」与「右侧最近」这通常能得到 $O(n)$ 时间、$O(1)$ 空间的简洁解法初始值的选取要有数学依据本题选n 1是因为任意两下标间最大距离不超过n - 1n 1足够充当「未覆盖」占位BFS 的-1标记法把答案数组初始化为-1既占位又判重省去单独的visited数组方向数组的抽象一维 BFS 用dirs {-1, 1}二维 BFS 用四方向或八方向本题是理解该抽象的最小规模样例。延伸阅读本文题解原文档LeetCode/821-830/821. 字符的最短距离简单.md模拟类题目索引Index/模拟.mdBFS 类题目索引Index/BFS.md仓库简介与使用方式README.md赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐leetcode 题解821. 字符的最短距离双向遍历解法全解析leetcode 题解821. 字符的最短距离双向遍历解法全解析 本篇技术指南基于本仓库题解 problems/821.shortest distance文档教程知识库LeetCode 821「字符的最短距离」多解法全解析从暴力双向扩展到 O(N) 两次遍历LeetCode 821「字符的最短距离」多解法全解析从暴力双向扩展到 O N 两次遍历 导读 本文围绕 LeetCode 821「字符的最短距离Short文档教程知识库宫水三叶的刷题日记 · LeetCode 2059转化数字的最小运算数——用双向 BFS 求解状态空间最短路径宫水三叶的刷题日记 · LeetCode 2059转化数字的最小运算数——用双向 BFS 求解状态空间最短路径 本文基于开源仓库 LogicStack Lee教程文档上一篇QQ群数据采集系统完整使用手册下一篇10分钟搞定Home Assistant Glow 3D打印外壳设计与组装教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
