942. DI String Match ------------E

Q:

Given a string S that only contains "I" (increase) or "D" (decrease), let N = S.length.

Return any permutation A of [0, 1, ..., N] such that for all i = 0, ..., N-1:

• If S[i] == "I", then A[i] < A[i+1]
• If S[i] == "D", then A[i] > A[i+1]

 

Example 1:

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

Example 2:

Input: "III"
Output: [0,1,2,3]

Example 3:

Input: "DDI"
Output: [3,2,0,1]

 

Note:

1. 1 <= S.length <= 10000
2. S only contains characters "I" or "D".

A:

find  a way to fill in the result vector

class Solution {
public:
    vector<int> diStringMatch(string S) {
        int N = S.length();
        vector<int> res(N+1,-1);
        if(S[N-1] == 'I')
            res[N] = N;
        int v = 0;
        if(S[N-1] == 'D')
            res[N] = v++;
        
        for(int i =0;i<N;++i){ // left->right, fill in the smaller by increasingly
            if(S[i] =='I')
                res[i] = v++;
        }
        for(int i =N-1; i >=0;--i){ //right->left, fill in the smaller
            if(S[i] =='D')
                res[i] = v++;
        }
        
        return res;
    }
};