942. DI String Match

Link: https://leetcode.com/problems/di-string-match/

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”.

---

題目翻譯:

給定僅包含“I”（增加）或“D”（減少）的字符串 S，令 N = S.length。

返回[0,1，…，N]的任何排列 A，使得對於所有 i = 0，…，N-1：

程式思路:

遇到遞增就給他最小值的元素，遇到遞減就給他最大值素，有點類似貪心演算法的感覺。

class Solution {
public:
    vector<int> diStringMatch(string S) {
        std::vector<int> result;
        int max = S.length();
        int min = 0;
        for(auto c : S)
        {
            if(c == 'I')
                result.emplace_back(min++);
            else if(c == 'D')
                result.emplace_back(max--);
        }
        result.emplace_back(max); // min 也可以
        return result;
    }
};