Description
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 <= 10000Sonly 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://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