给定一个字符串 S 和一个字符 C。返回一个代表字符串 S 中每个字符到字符串 S 中的字符 C 的最短距离的数组。
示例 1:
输入: S = "loveleetcode", C = 'e'
输出: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/shortest-distance-to-a-character 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
vector<int> shortestToChar(string S, char C) {
int i, j, left, right;
vector<int> ans(S.size());
vector<int> positionsC;
for(i = 0; i < S.size(); ++i)
{
if(S[i] == C)
positionsC.push_back(i);
}
positionsC.insert(positionsC.begin(),-20000);
positionsC.push_back(300000);
left = positionsC[0];
right = positionsC[1];
for(i = 0, j = 1; i < S.size(); ++i)
{
if(S[i] == C)
{
ans[i] = 0;
left = right;
right = positionsC[++j];
}
else
{
ans[i] = min(i-left,right-i);
}
}
return ans;
}
};