[LeetCode] 942. DI String Match 增減DI字元串比對

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]

• S[i] == "D"

  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"

   .

這道題給了一個隻有 'D' 和 'I' 兩個字母組成的字元串，表示一種 pattern，其中 'D' 表示需要下降 Decrease，即目前數字大于下個數字，同理，'i' 表示需要上升 Increase，即目前數字小于下個數字，讓傳回符合這個要求的任意一個數組，還有個要求是該數組必須是 [0, n] 之間的所有數字的一種全排列，其中n是給定 pattern 字元串的長度。這表明了傳回數組不能有重複數字，這裡一會上升一會下降的，很容易産生重複數字，難不成還要不停的檢測是否有重複數字麼，不，這樣太麻煩了，必須想一種生成方法來保證絕對不會有重複數字。對于上升來說，可以從0開始累加，而對于下降來說，則可以從n開始下降，這樣保證了在結束之前二者絕不會相遇，到最後一個數字的時候二者相同，再将這個相同數字加入即可，因為傳回的數組的個數始終會比給定字元串長度大1個，參見代碼如下：

class Solution {
public:
    vector<int> diStringMatch(string S) {
		vector<int> res;
		int n = S.size(), mn = 0, mx = n;
		for (char c : S) {
			if (c == 'I') res.push_back(mn++);
			else res.push_back(mx--);
		}
        res.push_back(mx);
		return res;
    }
};
           

Github 同步位址:

https://github.com/grandyang/leetcode/issues/942

參考資料：

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

https://leetcode.com/problems/di-string-match/discuss/194906/C%2B%2B-4-lines-high-low-pointers

https://leetcode.com/problems/di-string-match/discuss/194904/C%2B%2BJavaPython-Straight-Forward

[LeetCode All in One 題目講解彙總(持續更新中...)](https://www.cnblogs.com/grandyang/p/4606334.html)

喜歡請點贊，疼愛請打賞❤️~.~

微信打賞

Venmo 打賞