C++ very easy-to-understand non-reverse solution


  • 0

    The idea is very simple: Initiate the set with a single number 1, then iterate from 0 to n-1, for i-th iteration, we put the number i+2 into our set, so now our problem is where could I put the number in.

    If current character is 'I', it's very straightforward, we put the new number in the end.

    If current character is 'D', we must find a position to insert our new number because it is the largest one until now. So here we should look backward to check whether we are in a consecutive decreasing sequence or not. If we are in a decreasing sequence, we can put our new number in the front of the head of this sequence to maintain the decreasing property. How to find the head of the sequence, you can check previous characters one by one, I use a counter to count the consecutive 'D's.

    For example:
    The given string is IIDDI, the initial set has the single number 1

    IIDDI    1(2)    push back 2
    ^
    
    
    IIDDI    12(3)    push back 3
     ^
    
    
    IIDDI    12(4)3    insert 4 before the head of decreasing sequence, and the sequence is empty, so we insert it before the last one
      ^
    
    
    IIDDI    12(5)43    insert 5 before the head of decreasing sequence, head is 4, so we insert 5 before 4
       ^
    
    
    IIDDI    12543(6)    push back 6
        ^
    
    class Solution {
    public:
        vector<int> findPermutation(string s) {
            vector<int> res({1});
            int c = 0; // count consecutive 'D's
            for (int i = 0; i < (int)s.size(); ++i) {
                if (s[i] == 'I') {
                    res.push_back(i+2);
                    c = 0;
                } else {
                    res.insert(res.begin()+i-c, i+2);
                    ++c;
                }
            }
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.