821. 字符的最短距离#

题目#

1
给定一个字符串 S 和一个字符 C
2

3
返回一个代表字符串 S 中每个字符到字符串 S 中的字符 C 的最短距离的数组。
4

5
示例 1：
6

7
输入：s = "loveleetcode", c = "e"
8

9
输出：[3,2,1,0,1,0,0,1,2,2,1,0]
10

11
解释：字符 'e' 出现在下标 3、5、6 和 11 处（下标从 0 开始计数）
12

13
距下标 0 最近的 'e' 出现在下标 3 ，所以距离为 abs(0 - 3) = 3
14

15
距下标 1 最近的 'e' 出现在下标 3 ，所以距离为 abs(1 - 3) = 2
16

17
对于下标 4 来说，出现在下标 3 和下标 5 处的 'e' 都离它最近。
18

19
但距离是一样的 abs(4 - 3) == abs(4 - 5) = 1
20

21
距下标 8 最近的 'e' 出现在下标 6 ，所以距离为 abs(8 - 6) = 2
22
示例 2：
23

24
输入：s = "aaab", c = "b"
25
输出：[3,2,1,0]

题目思路#

建立一个 vector，存储遍历字符串后等于输入字符 c 的位置下标；
对于每一个位置，将其减去数组中的值，取绝对值，并返回其中最小的值；
min(abs(i - pos[j]), abs(i - pos[j + 1])) 中会出现数组长度为一的特殊情况，此处的特殊情况之后会进一步优化。

题目代码#

代码块#

1
class Solution {
2
    public int[] shortestToChar(String s, char c){
3
        // 双重for循环查找
4
        int n = s.length();
5
        int[] res = new int[n];
6
        Arrays.fill(res, n + 1);
7
        for (int i = 0, j = -1; i < n; i++) {
8
            if (s.charAt(i) == c) {
9
                j = i;
10
            }
11
            if (j != -1) {
12
                res[i] = i - j;
13
            }
14
        }
15
        for (int i = n - 1, j = -1; i >= 0; i--) {
16
            if (s.charAt(i) == c) {
17
                j = i;
18
            }
19
            if (j != -1) {
20
                res[i] = Math.min(res[i], j - i);
21
            }
22
        }
23
        return res;
24
    }
25
}

1
class Solution {
2
public:
3
    vector<int> shortestToChar(string s, char c) {
4
        int n = s.size();
5
        vector<int> pos;
6
        vector<int> ans(n, n);
7

8
        for(int i = 0; i < n; i++)
9
        {
10
            if(s[i] == c) pos.push_back(i);
11
        }
12

13
        for(int i = 0; i < n; i++)
14
        {
15
            int tmp = 0;
16
            if(pos.size() != 1)
17
            {
18
                for(int j = 0; j < pos.size() - 1; j++)
19
                {
20
                    tmp = min(abs(i - pos[j]), abs(i - pos[j + 1]));
21
                    if(ans[i] > tmp) ans[i] = tmp;
22
                }
23
            }
24
            else
25
            {
26
                ans[i] = abs(i - pos[0]);
27
            }
28

29
        }
30
        return ans;
31
    }
32
};

1
func shortestToChar(s string, c byte) []int {
2
    n := len(s)
3

4
    ans := make([]int, n)
5
    pos := make([]int, 0)
6

7
    for i := 0; i < n; i++ {
8
        if s[i] == c {
9
            pos = append(pos, i)
10
        }
11
    }
12

13
    for i := 0; i < n; i++ {
14
        if s[i] != c {
15
            ans[i] = min(pos, i)
16
        } else {
17
            ans[i] = 0
18
        }
19
    }
20

21
    return ans
22
}
23

24
func min(num []int, n int) int {
25
    min := 10000 //因为最长为10000
26

27
    for i := 0; i < len(num); i++ {
28
        if min > abs(n - num[i]) {
29
            min = abs(n - num[i])
30
        }
31
    }
32

33
    return min
34
}
35

36
func abs(a int) int {
37
    if a < 0 {
38
        return -a
39
    }
40

41
    return a
42
}

复杂度#

时间复杂度：O( $n*k$ )，n 是 s 的长度，k 是字符 c 在字符串中出现的次数，k <= n。
空间复杂度：O(k)，k 为字符 c 出现的次数，这是记录字符 c 出现下标的辅助数组消耗的空间。