821. Shortest Distance to a Character

Given a string s and a character c that occurs in s, return an array of integers answer where answer.length == s.length and answer[i] is the shortest distance from s[i] to the character c in s.

Example 1:

Input: s = "loveleetcode", c = "e"
Output: [3,2,1,0,1,0,0,1,2,2,1,0]

Example 2:

Input: s = "aaab", c = "b"
Output: [3,2,1,0]

Constraints:

• 1 <= s.length <= 104
• s[i] and c are lowercase English letters.
• c occurs at least once in s.

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; 
    }
}

从左往右扫描再从右往左扫描，碰见不是default数的，就看它的左/右边可不可以更新。小小dp，大大惊喜

https://leetcode.com/problems/shortest-distance-to-a-character/discuss/126116/Concise-java-solution-with-detailed-explanation.-Easy-understand!!!