宫水三叶的刷题日记：LeetCode 821 字符的最短距离——两次遍历模拟与多源 BFS 双解法详解

• 教程
• 文档

导读

本文基于「宫水三叶的刷题日记」刷穿 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^4；
• s[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: vector<int> shortestToChar(string s, char c) { int n = s.length(); vector<int> 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 ans

TypeScript 实现

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 开始一直保持为 3，j - i恒等于3 - i，与正向结果相同，min取后结果不变。

再以s = "loveleetcode", c = "e"为例，正向遍历只能保证每个位置记录的是「到左侧最近e」的距离，例如下标 7（'t'）正向得到7 - 6 = 1，反向时最近e仍在下标 6，得到6 - 7 = -1的绝对值为 1，min(1, 1) = 1；而下标 9（'d'）正向得到9 - 6 = 3，反向时最近e在下标 11，得到11 - 9 = 2，min(3, 2) = 2，正好与示例输出吻合。

复杂度

• 时间复杂度：$O(n)$，两次线性扫描；
• 空间复杂度：$O(1)$（不计返回答案数组本身，仅使用常数个辅助变量）。

解法二：多源 BFS（一维数组上的多起点扩散）

核心思路

把问题转化为「从多个源点出发的最短路」问题：所有出现c的下标都是源点（距离为 0），在一维数组上允许向左右两个方向移动一步，求每个位置到最近源点的距离。这正是「多源 BFS」在数组上的直接应用。

实现要点：

1. 初始化ans全部为-1，同时把-1作为「是否已被访问」的标记；
2. 遍历一遍字符串，把所有等于c的下标入队（Deque），并将对应ans[i]置为0；
3. 定义方向数组dirs = {-1, 1}，代表向左右各扩散一步；
4. 从队头取出下标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); Deque<Integer> 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: vector<int> shortestToChar(string s, char c) { int n = s.length(); vector<int> ans(n, -1); deque<int> d; for (int i = 0; i < n; i++) { if (s[i] == c) { d.push_back(i); ans[i] = 0; } } vector<int> 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 ans

TypeScript 实现

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)$ 个下标。

两种解法对比与选用建议

在仓库 Index/BFS.md 收录的题目（如 90. 子集 II、397. 整数替换、403. 青蛙过河、429. N 叉树的层序遍历等）中，BFS 通常作用于树、图或二维网格；本题的特殊之处在于把 BFS 用在一维数组上，方向数组只有{-1, 1}两个取值，是理解「多源 BFS 判重与分层扩散」的最佳入门样例。而两次遍历模拟则属于 Index/模拟.md 所归纳的字符串模拟类题目（如 38. 外观数列、58. 最后一个单词的长度、482. 密钥格式化等）中的典型套路——「正反两次扫描 + 前缀/后缀信息合并」，这一套路在「蜡烛之间的盘子」等稍复杂题目中同样适用。

刷题要点小结

1. 看到「到最近某个位置的距离」，先想是否可以用两次扫描分别维护「左侧最近」与「右侧最近」，这通常能得到 $O(n)$ 时间、$O(1)$ 空间的简洁解法；
2. 初始值的选取要有数学依据：本题选n + 1，是因为任意两下标间最大距离不超过n - 1，n + 1足够充当「未覆盖」占位；
3. BFS 的-1标记法：把答案数组初始化为-1，既占位又判重，省去单独的visited数组；
4. 方向数组的抽象：一维 BFS 用dirs = {-1, 1}，二维 BFS 用四方向或八方向，本题是理解该抽象的最小规模样例。

延伸阅读

• 本文题解原文档：LeetCode/821-830/821. 字符的最短距离（简单）.md
• 模拟类题目索引：Index/模拟.md
• BFS 类题目索引：Index/BFS.md
• 仓库简介与使用方式：README.md

• 教程
• 文档