题目

原题在此

Given a string s and a character c that occurs in s, return an array of integers answer where answer.length == s.length and answer[i] is the shortest distance from s[i] to the character c in s.

Example 1:
Input: s = "loveleetcode", c = "e"
Output: [3,2,1,0,1,0,0,1,2,2,1,0]

Example 2:
Input: s = "aaab", c = "b"
Output: [3,2,1,0]

Constraints:
1 <= s.length <= $10^4$
s[i] and c are lowercase English letters.
c occurs at least once in s.

解析

找到第一个和最后一个c, 第一遍从第一个c到s.end()按规则填写, 第二遍从最后一个c到s.begin()按规则填写或如果已填写的值较小则跳过.

代码

c++

class Solution {
public:
    vector<int> shortestToChar(string s, char c) {
        vector<int> res(s.size(), INT_MAX);
        int first = s.find(c), last = s.find_last_of(c);
        int n = s.size(), tmp = 0;
        for(int i = first; i < n; ++i) {
            if(s[i] == c) tmp = 0;
            res[i] = tmp++;
        }
        tmp = 0;
        for(int i = last; i >= 0; --i) {
            if(!res[i]) tmp = 0;
            res[i] = min(res[i], tmp++);
        }
        return res;
    }
};