Problem
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 <= S.length <= 10000
S
Ā only contains charactersĀ"I"
Ā orĀ"D"
.
Solution: Greedy
“I” -> use the smallest possible number
“D” -> use the largest possible number
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua, 44 ms class Solution { public: vector<int> diStringMatch(string S) { const int n = S.length(); vector<int> ans; int lo = 0; int hi = n; for (char c : S) { if (c == 'I') ans.push_back(lo++); else ans.push_back(hi--); } ans.push_back(lo); return ans; } }; |