题目描述

给定一个字符串 S 和一个字符 C。返回一个代表字符串 S 中每个字符到字符串 S 中的字符 C 的最短距离的数组。

样例

输入: S = "loveleetcode", C = 'e'
输出: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

提示

• 字符串 S 的长度范围为 [1, 10000]。
• C 是一个单字符，且保证是字符串 S 里的字符。
• S 和 C 中的所有字母均为小写字母。

算法

(宽度优先搜索 / BFS) $O(n)$

1. 简单的宽搜策略，相当于求每个位置距离某个起点的最短距离。
2. 首先将所有字符为 C 的位置入队，其位置的距离为 0，其余位置为正无穷。
3. 然后使用队列进行宽搜，每次可以每个位置可以向左向右扩展，同时更新距离。
4. 最后的距离数组就是答案。

时间复杂度

• 每个位置最多进队一次，出队一次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要额外的队列空间 $O(n)$，以及存储答案的空间 $O(n)$，总空间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    vector<int> shortestToChar(string S, char C) {
        int n = S.length();
        vector<int> dis(n, 10001);
        queue<int> q;
        for (int i = 0; i < n; i++)
            if (S[i] == C) {
                q.push(i);
                dis[i] = 0;
            }

        while (!q.empty()) {
            int sta = q.front();
            q.pop();
            if (sta + 1 < n && dis[sta + 1] > dis[sta] + 1) {
                dis[sta + 1] = dis[sta] + 1;
                q.push(sta + 1);
            }
            if (sta - 1 >= 0 && dis[sta - 1] > dis[sta] + 1) {
                dis[sta - 1] = dis[sta] + 1;
                q.push(sta - 1);
            }
        }

        return dis;
    }
};