Given a stringS and a characterC, return an array of integers representing the shortest distance from the characterCin the string.

Example 1:

Input: S = "loveleetcode", C = 'e'
Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

Note:

1. Sstring length is in [1, 10000].
2. Cis a single character, and guaranteed to be in stringS
3. All letters inSandCare lowercase.

这道题可以直接暴力求解，记录一下字符C出现的所有index，再对S中的字符逐个求最小距离。

还有一个更简单一点的解法，因为距离C最短的距离要么是到左边最近的C的距离，要么是到右边最近的C的距离，所以可以先从左到右遍历S，记录每个字符到上一次出现的C的距离。再从右向左遍历S，记录每个字符到上一次出现的C的距离，这两个值中较小的就是最短距离。

class Solution {
    public int[] shortestToChar(String S, char C) {
        if(S == null || S.length() == 0)
            return new int[0];

        int[] res = new int[S.length()];
        for(int i = 0; i < res.length; i++)
            res[i] = Integer.MAX_VALUE;

        int prev = -1;
        for(int i = 0; i < res.length; i++) {
            char c = S.charAt(i);

            if(c == C) {
                prev = i;
            } else {
                if(prev != -1) {
                    res[i] = Math.min(res[i], i - prev);
                }
            }
        }

        prev = -1;
        for(int i = res.length - 1; i >= 0; i--) {
            char c = S.charAt(i);

            if(c == C) {
                prev = i;
                res[i] = 0;
            } else {
                if(prev != -1) {
                    res[i] = Math.min(res[i], prev - i);
                }
            }
        }

        return res;
    }
}