LeetCode 821. 字符的最短距离

Categories:

题目描述
思路分析
1. 解法一：双向遍历（推荐）
相似题目

题目描述

✅ 821. 字符的最短距离

思路分析

解法一：双向遍历（推荐）

核心思路：

从左到右记录最近目标字符的位置，计算左侧距离。

从右到左再计算右侧距离并取最小值。

合并两次遍历结果。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(n)，用于结果数组。

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;
            }
            res[i] = Math.min(res[i], prev - i);
        }

        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
		}
		d := prev - i
		if d < res[i] {
			res[i] = d
		}
	}

	return res
}

相似题目

题目	难度	考察点
849. 到最近的人的最大距离	中等	双向遍历
848. 字母移位	中等	字符串
1163. 按字典序排在最后的子串	困难	双指针
345. 反转字符串中的元音字母	简单	字符串
541. 反转字符串 II	简单	字符串

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/53256683