题目

给你一个字符串 s 和一个字符 c ，且 c 是 s 中出现过的字符。

返回一个整数数组 answer ，其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它最近的字符 c 的距离。

两个下标 i 和 j 之间的距离为 abs(i - j) ，其中 abs 是绝对值函数。

来源：力扣（LeetCode）

解答

从左到右遍历一次，再从右到左遍历一次即可。

第一次遍历找的是距离左边最近的距离，第二次是右边。

代码如下：

class Solution {
public:
    vector<int> shortestToChar(string s, char c) {
        int n = s.size();
        vector<int> ret(n, n + 1);

        int pos = -1;
        for (int i = 0; i < n; ++i) {
            if (s[i] == c) {
                pos = i;
            }
            if (pos != -1) {
                ret[i] = i - pos;
            }
        }

        pos = -1;
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == c) {
                pos = i;
            }
            if (pos != -1) {
                ret[i] = min(ret[i], pos - i);
            }
        }

        return ret;
    }
};