Easy

题目描述

给你一个字符串 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 中至少出现一次

解题思路

解题思路

这道题要求计算字符串中每个位置到最近目标字符的距离。有几种解法：

方法一：双指针（推荐） 使用双指针技巧，分别从左到右和从右到左扫描两次：

  • 第一次扫描：记录每个位置到左侧最近目标字符的距离
  • 第二次扫描：记录每个位置到右侧最近目标字符的距离，并与左侧距离取最小值

具体实现：用 prev 记录上一个目标字符的位置，初始化为一个很大的负数。第一次遍历时，如果当前字符是目标字符，更新 prev；否则计算距离。第二次遍历时，用类似方法从右往左计算距离。

方法二：预处理位置 先遍历一次字符串，记录所有目标字符的位置，然后对每个位置用二分查找找到最近的目标字符位置。

方法三：暴力法 对每个位置，向左右两边搜索最近的目标字符，时间复杂度较高。

双指针法只需要两次遍历，时间复杂度最优，空间复杂度也最小，是最佳解法。

代码实现

class Solution {
public:
    vector<int> shortestToChar(string s, char c) {
        int n = s.length();
        vector<int> answer(n, INT_MAX);
        
        // 从左到右扫描
        int prev = -10000;
        for (int i = 0; i < n; i++) {
            if (s[i] == c) {
                prev = i;
            }
            answer[i] = i - prev;
        }
        
        // 从右到左扫描
        prev = 10000;
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == c) {
                prev = i;
            }
            answer[i] = min(answer[i], prev - i);
        }
        
        return answer;
    }
};

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        n = len(s)
        answer = [float('inf')] * n
        
        # 从左到右扫描
        prev = -10000
        for i in range(n):
            if s[i] == c:
                prev = i
            answer[i] = i - prev
        
        # 从右到左扫描
        prev = 10000
        for i in range(n - 1, -1, -1):
            if s[i] == c:
                prev = i
            answer[i] = min(answer[i], prev - i)
        
        return answer

public class Solution {
    public int[] ShortestToChar(string s, char c) {
        int n = s.Length;
        int[] answer = new int[n];
        Array.Fill(answer, int.MaxValue);
        
        // 从左到右扫描
        int prev = -10000;
        for (int i = 0; i < n; i++) {
            if (s[i] == c) {
                prev = i;
            }
            answer[i] = i - prev;
        }
        
        // 从右到左扫描
        prev = 10000;
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == c) {
                prev = i;
            }
            answer[i] = Math.Min(answer[i], prev - i);
        }
        
        return answer;
    }
}

var shortestToChar = function(s, c) {
    const n = s.length;
    const answer = new Array(n).fill(Infinity);
    
    // 从左到右扫描
    let prev = -10000;
    for (let i = 0; i < n; i++) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

项目复杂度
时间复杂度O(n)
空间复杂度O(1)

说明：

  • 时间复杂度：需要对字符串进行两次遍历，每次遍历时间复杂度为 O(n)
  • 空间复杂度：除了返回数组外，只使用了常数级别的额外空间

相关题目