821.Shortest Distance to a Character
821.Shortest Distance to a Character
难度:Easy
给定一个字符串 S 和一个字符 C。返回一个代表字符串 S 中每个字符到字符串 S 中的字符 C 的最短距离的数组。
示例 1:
1
输入: S = "loveleetcode", C = 'e'
2
输出: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]
3
说明:
Copied!
字符串 S 的长度范围为 [1, 10000]。 C 是一个单字符,且保证是字符串 S 里的字符。 S 和 C 中的所有字母均为小写字母。
代码如下:
1
class Solution {
2
public:
3
vector<int> shortestToChar(string S, char C) {
4
vector<int> cc;
5
int len=S.size();
6
vector<int> index;
7
for(auto i:S)
8
if(i==C) {cc.push_back(0);
9
index.push_back(cc.size()-1);}
10
else cc.push_back(len);
11
int start=1;
12
for(int i=index[0]+1;i<len;i++)
13
if(cc[i]) cc[i]=start++;
14
else start=1;
15
start=1;
16
for(int i=index[index.size()-1]-1;i>=0;i--)
17
if(cc[i]) cc[i]=min(cc[i],start++);
18
else start=1;
19
return cc;
20
}
21
};
Copied!
Copy link