821. Shortest Distance to a Character

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

/** "loveleetcode" "e"
 *  1. put 0 at all position equals to e, and max at all other position
 *     we will get [max, max, max, 0, max, 0, 0, max, max, max, max, 0]
 *  2. scan from left to right, if =max, skip, else dist[i+1] = Math.min(dp[i] + 1, dp[i+1]), 
 *     we can get [max, max, max, 0, 1, 0, 0, 1, 2, 3, 4, 0]
 *  3. scan from right to left, use dp[i-1] = Math.min(dp[i] + 1, dp[i-1])
 *     we will get[3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0] 
 */
class Solution {
    public int[] shortestToChar(String s, char c) {
        int n = s.length();
        int[] dist = new int[n];
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == c) continue;
            dist[i] = Integer.MAX_VALUE;
        }
        for (int i = 0; i < n-1; i++) {
            if (dist[i] == Integer.MAX_VALUE) continue;
            else dist[i + 1] = Math.min(dist[i+1], dist[i] + 1);
        }
        for (int i = n-1; i > 0; i--) {
            dist[i-1] = Math.min(dist[i-1], dist[i] + 1);
        }
        return dist; 
    }
}