LeetCode-942. DI String Match

LeetCode-942. 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"​​.

题解：

class Solution {public: vector diStringMatch(string S) { int n = S.length(); int maxi = n, mini = 0; vector ans; for (int i = 0; i < n; i++) { if (S[i] == 'I') { ans.push_back(mini++); while (S[i] == S[i + 1]) { i++; ans.push_back(mini++); } } else { ans.push_back(maxi--); while (S[i] == S[i + 1]) { i++; ans.push_back(maxi--); } } } if (S[n - 1] == 'I') { ans.push_back(mini); } else { ans.push_back(maxi); } return ans; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。