942. DI String Match

第一次写了DFS然后TLE
后来看了别人的答案，发现其实是一个变相的dp
原始问题S e.g.

"IDID"
Output: [0,4,1,3,2]

可以分解成子问题
If we see 'I' and use the min number, we can guarantee that all numbers are larger than the current number, so what we choose later doesn't matter
The same idea, if we see 'D' and use the max number, we can guarantee that all numbers are smaller than the current number, so what we choose later doesn't matter
String S           numbers        result   
"IDID"               [0, 4]             0 ->  'I' will always be satisfied
"DID"                [1, 4]             4 ->  'D' will always be satisfied
"ID"                   [1, 3]             1 ->  'I' will always be satisfied


class Solution {
    public int[] diStringMatch(String S) {
        if (S == null) {
            return new int[0];
        }
        int left = 0;
        int right = S.length();
        int[] result = new int[S.length() + 1];
        for (int i = 0; i < S.length(); i++) {
            if (S.charAt(i) == 'I') {
                result[i] = left;
                left++;
            } else {
                result[i] = right;
                right--;
            }
        }
        result[S.length()] = left;
        return result;
    }
}