LeetCode 821. 字符的最短距离

约 4 分钟
文章信息 7 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 2-5 腾讯 百度
标签
数组 字符串 双指针

题目描述

✅ 821. 字符的最短距离

image-20260928225059880

image-20260928225059887

题意分析

对字符串中的每个下标 i，求它到最近一次出现的目标字符 c 的下标距离。距离是两个下标之差的绝对值，目标字符自身的距离为 0；题目保证 c 至少出现一次。

解法：左右方向距离预处理

核心思路

[!blue]

对某个位置来说，左边越靠近它的目标字符距离越小，右边也一样。因此不必检查所有目标位置，只需比较“左侧最近目标”和“右侧最近目标”两个候选，当前位置恰好是目标时也包含在内。

从左向右扫描，用 prev 保存截至当前位置最后一次出现 c 的下标。若当前字符就是 c，先令 prev = i，然后把 i - prev 写入 res[i]。这遍结束后，数组记录了每个位置的左侧候选距离。

再从右向左扫描，此时 prev 记录右侧最近的目标下标，右侧距离是 prev - i。用它与已有的 res[i] 取较小值，就得到完整答案。

某一侧还没有遇到目标时，用哨兵代替：正向初值为 -n，反向初值为 2*n。它们产生的距离至少为 n，而任何真实距离至多为 n-1。由于目标一定存在，虚假的候选最终一定会被另一侧的真实距离替换。

解题步骤

  1. 建立长度为 n 的结果数组，将 prev 初始化为 -n。
  2. 正向扫描，遇到 c 时先更新 prev，再将 i - prev 写入结果。
  3. 把 prev 重新设为 2*n，从最后一个字符开始反向扫描。
  4. 同样先更新目标位置，再用 prev - i 与当前结果取最小值，最后返回结果数组。

代码实现

class Solution {
    public int[] shortestToChar(String s, char c) {
        int n = s.length();
        int[] res = new int[n];

        // 没有左侧目标时，用大于任何真实距离的候选
        int prev = -n;

        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == c) {
                prev = i;
            }

            res[i] = i - prev;
        }

        // 反向重新设置无目标哨兵，随后与左距取最小
        prev = 2 * n;

        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == c) {
                prev = i;
            }

            int rightDist = prev - i;

            if (rightDist < res[i]) {
                res[i] = rightDist;
            }
        }

        return res;
    }
}

func shortestToChar(s string, c byte) []int {
    n := len(s)
    res := make([]int, n)

    // 没有左侧目标时，用大于任何真实距离的候选
    prev := -n
    for i := 0; i < n; i++ {
        if s[i] == c {
            prev = i
        }
        res[i] = i - prev
    }

    // 反向重新设置无目标哨兵，随后与左距取最小
    prev = 2 * n
    for i := n - 1; i >= 0; i-- {
        if s[i] == c {
            prev = i
        }
        right := prev - i
        if right < res[i] {
            res[i] = right
        }
    }

    return res
}

复杂度分析

  • 时间复杂度：$O(n)$，n 为字符串长度，正向和反向各扫描一次。
  • 空间复杂度：不计结果数组为 $O(1)$；结果数组本身需要 $O(n)$ 空间。

关键点总结

[!green]

  • 每一侧只有最近的目标位置可能成为最优候选，两侧取最小即可。
  • 当前字符命中目标时，先更新位置，才能得到自身距离 0。
  • 哨兵距离必须大于所有真实距离，不能把“这一侧没有目标”误当成一个很近的目标。

易错点总结

[!yellow]

  • 正向用 -1 当作目标位置：产生的假距离可能比真正的右侧目标更近；这里用 -n 保证不会干扰最终最小值。
  • 反向直接覆盖结果：会丢掉可能更近的左侧目标，应取两侧最小值。
  • 两遍使用相同的减法顺序：正向是 i - prev，反向是 prev - i，距离应始终非负。
  • 先算距离再更新 prev：会让目标字符自身得到非零距离。

相似题目

题目 难度 关联与区别
542. 01 矩阵 中等 二维最近目标可用多源BFS，本题是一维序列，左右两次扫描就能传播最近目标距离。
244. 最短单词距离 II 中等 同样从目标出现位置查询最短距离，原题有很多词对查询，本题固定一个字符并回答全部位置。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/53256683
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！