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"
, thenA[i] < A[i+1]
- If
S[i] == "D"
, thenA[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 <= S.length <= 10000
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; } };
No comments:
Post a Comment