942. DI String Match（python+cpp）-白红宇

942. DI String Match（python+cpp）

阅读量：3702 次

发布时间：2019-05-21

本文共 1469 字，大约阅读时间需要 4 分钟。

题目：

Given a string Sthat 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".

解释：

注意，output的长度比input的长度多1。

python代码：

class Solution:    def diStringMatch(self, S):        """        :type S: str        :rtype: List[int]        """        init =list(range(len(S)+1))        result=[]        for s in S:            if s=='D':                result.append(init.pop())            else:                result.append(init.pop(0))        return result+init

c++代码：

#include
   
    using namespace std;class Solution {
   public:    vector
    
      diStringMatch(string S) {
           deque
     
       init;        for (int i=0;i<=S.size();i++)            init.push_back(i);        vector
      
        result;        for (auto s:S)        {
               if (s=='D')            {
                   result.push_back(init.back());                init.pop_back();            }            else            {
                   result.push_back(init.front());                init.pop_front();            }        }        result.push_back(init.back());        return result;    }};