给你一个字符串 s 和一个字符 c ，且 c 是 s 中出现过的字符。
返回一个整数数组 answer ，其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i
到离它 最近 的字符 c 的 距离 。
两个下标 i 和 j 之间的 距离 为 abs(i - j) ，其中 abs 是绝对值函数。
示例 1：
**输入：** s = "loveleetcode", c = "e"
**输出：** [3,2,1,0,1,0,0,1,2,2,1,0]
**解释：** 字符 'e' 出现在下标 3、5、6 和 11 处（下标从 0 开始计数）。
距下标 0 最近的 'e' 出现在下标 3 ，所以距离为 abs(0 - 3) = 3 。
距下标 1 最近的 'e' 出现在下标 3 ，所以距离为 abs(1 - 3) = 2 。
对于下标 4 ，出现在下标 3 和下标 5 处的 'e' 都离它最近，但距离是一样的 abs(4 - 3) == abs(4 - 5) = 1 。
距下标 8 最近的 'e' 出现在下标 6 ，所以距离为 abs(8 - 6) = 2 。
示例 2：
**输入：** s = "aaab", c = "b"
**输出：** [3,2,1,0]
提示：
1 <= s.length <= 104s[i] 和 c 均为小写英文字母- 题目数据保证
c 在 s 中至少出现一次
方法一：两次遍历
问题可以转换成，对 s 的每个下标 i，求
- s[i] 到其左侧最近的字符 c 的距离
- s[i] 到其右侧最近的字符 c 的距离
这两者的最小值。
对于前者，我们可以从左往右遍历 s，若 s[i]=c 则记录下此时字符 c 的的下标 idx。遍历的同时更新 answer}[i]=i-\textit{idx。
对于后者，我们可以从右往左遍历 s，若 s[i]=c 则记录下此时字符 c 的的下标 idx。遍历的同时更新 answer}[i]=\min(\textit{answer}[i],\textit{idx}-i)。
代码实现时，在开始遍历的时候 idx 可能不存在，为了简化逻辑，我们可以用 -n 或 2n 表示，这里 n 是 s 的长度。
[sol1-Python3]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution:
def shortestToChar(self, s: str, c: str) -> List[int]:
n = len(s)
ans = [0] * n
idx = -n
for i, ch in enumerate(s):
if ch == c:
idx = i
ans[i] = i - idx
idx = 2 * n
for i in range(n - 1, -1, -1):
if s[i] == c:
idx = i
ans[i] = min(ans[i], idx - i)
return ans
|
[sol1-C++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
vector<int> shortestToChar(string s, char c) {
int n = s.length();
vector<int> ans(n);
for (int i = 0, idx = -n; i < n; ++i) {
if (s[i] == c) {
idx = i;
}
ans[i] = i - idx;
}
for (int i = n - 1, idx = 2 * n; i >= 0; --i) {
if (s[i] == c) {
idx = i;
}
ans[i] = min(ans[i], idx - i);
}
return ans;
}
};
|
[sol1-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int[] shortestToChar(String s, char c) {
int n = s.length();
int[] ans = new int[n];
for (int i = 0, idx = -n; i < n; ++i) {
if (s.charAt(i) == c) {
idx = i;
}
ans[i] = i - idx;
}
for (int i = n - 1, idx = 2 * n; i >= 0; --i) {
if (s.charAt(i) == c) {
idx = i;
}
ans[i] = Math.min(ans[i], idx - i);
}
return ans;
}
}
|
[sol1-C#]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public class Solution {
public int[] ShortestToChar(string s, char c) {
int n = s.Length;
int[] ans = new int[n];
for (int i = 0, idx = -n; i < n; ++i) {
if (s[i] == c) {
idx = i;
}
ans[i] = i - idx;
}
for (int i = n - 1, idx = 2 * n; i >= 0; --i) {
if (s[i] == c) {
idx = i;
}
ans[i] = Math.Min(ans[i], idx - i);
}
return ans;
}
}
|
[sol1-Golang]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| func shortestToChar(s string, c byte) []int {
n := len(s)
ans := make([]int, n)
idx := -n
for i, ch := range s {
if byte(ch) == c {
idx = i
}
ans[i] = i - idx
}
idx = n * 2
for i := n - 1; i >= 0; i-- {
if s[i] == c {
idx = i
}
ans[i] = min(ans[i], idx-i)
}
return ans
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
|
[sol1-JavaScript]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| var shortestToChar = function(s, c) {
const n = s.length;
const ans = new Array(n).fill(0);
for (let i = 0, idx = -n; i < n; ++i) {
if (s[i] === c) {
idx = i;
}
ans[i] = i - idx;
}
for (let i = n - 1, idx = 2 * n; i >= 0; --i) {
if (s[i] == c) {
idx = i;
}
ans[i] = Math.min(ans[i], idx - i);
}
return ans;
};
|
[sol1-C]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #define MIN(a, b) ((a) < (b) ? (a) : (b))
int* shortestToChar(char * s, char c, int* returnSize){
int n = strlen(s);
int *ans = (int *)malloc(sizeof(int) * n);
for (int i = 0, idx = -n; i < n; ++i) {
if (s[i] == c) {
idx = i;
}
ans[i] = i - idx;
}
for (int i = n - 1, idx = 2 * n; i >= 0; --i) {
if (s[i] == c) {
idx = i;
}
ans[i] = MIN(ans[i], idx - i);
}
*returnSize = n;
return ans;
}
|
复杂度分析
