0821. Shortest Distance to a Character #

题目 #

给定字符串 s 和一个字符 c，且 c 是 s 中出现过的字符。
返回整数数组 answer，其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离他最近的字符 c 的距离。
两个下标 i 和 j 之间的距离为 abs(i - j)，其中 abs 是绝对值函数。

思路 #

双向遍历 #

BFS #

代码 #

双向遍历 #

class Solution {
    public int[] shortestToChar(String s, char c) {
        /** 双向扫描数组 */
        int[] ans = new int[s.length()];
        for (int i = 0; i < ans.length; i++) ans[i] = Integer.MAX_VALUE;
        int ptr = -1;
        /** 从后向前扫描数组 */
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == c) ptr = i;
            if (ptr >= i) ans[i] = ptr -i;
        }
        /** 从前向后扫描数组 */
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == c) ptr = i;
            if (ptr <= i) ans[i] = Math.min(ans[i], i - ptr);
        }
        return ans;
    }
}