双指针解决字符的最短距离

暴力解法

class Solution {
    public int[] shortestToChar(String s, char c) {
        int len = s.length();
        ArrayList<Integer> index = new ArrayList<>();
        int i = 0;
        for(i = 0; i < len; i++){
            if(s.charAt(i) == c){
                index.add(i);
            }
        }
        int[] res = new int[len];
        for(i = 0; i < len; i++){
            int min = Integer.MAX_VALUE;
            for(int j = 0; j < index.size(); j++){
                min = Math.min(min, Math.abs(i - index.get(j)));
            }
            res[i] = min;     
        }
        return res;
    }
}

双指针降低时间复杂度

不用在索引上依次去遍历目标字符的索引集合找到最近的，而是在第一层循环中更新最近的索引位置。

class Solution {
    public int[] shortestToChar(String s, char c) {
        int len = s.length();
        int[] res = new int[len];
        int l = s.indexOf(c), r = s.indexOf(c, l+1);
        for(int i = 0; i < s.length(); i++){
            res[i] = Math.abs(l - i);
            if(r != -1){
                res[i] = Math.min(res[i], r - i);
                if(i == r){
                    res[i] = 0;
                    l = r;
                    r = s.indexOf(c, r + 1);
                }
            }
        }
        return res;
    }
}