821. Shortest Distance to a Character

Stack

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
29
class Solution {
    public int[] shortestToChar(String s, char c) {
        int[] res = new int[s.length()];

        int prevCIndex = Integer.MIN_VALUE / 2;
        Stack<Integer> indexStack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char curr = s.charAt(i);
            if (curr == c) {
                // 计算栈中字符的最近距离并更新 prevCIndex
                while (!indexStack.isEmpty()) {
                    int index = indexStack.pop();
                    res[index] = Math.min(i - index, index - prevCIndex);
                }
                prevCIndex = i;
            } else {
                indexStack.push(i);
            }
        }

        // 处理 s = "abaa", c = 'b' 这样的场景
        while (!indexStack.isEmpty()) {
            int index = indexStack.pop();
            res[index] = index - prevCIndex;
        }

        return res;
    }
}

Traverse

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
class Solution {
    public int[] shortestToChar(String s, char c) {
        int[] res = new int[s.length()];
        Arrays.fill(res, s.length());

        for (int i = 0, j = -1; i < s.length(); i++) {
            if (s.charAt(i) == c) {
                j = i;
            }
            if (j != -1) {
                // 出现了 c
                res[i] = i - j;
            }
        }

        for (int i = s.length() - 1, j = -1; i >= 0; i--) {
            if (s.charAt(i) == c) {
                j = i;
            }
            if (j != -1) {
                res[i] = Math.min(res[i], j - i);
            }
        }

        return res;
    }
}

References

821. Shortest Distance to a Character