[ Add to List 484. Find Permutation] C++_Stack or Two Pointers


  • 0

    Space: O(1)

    class Solution 
    public:
    vector<int> findPermutation(string s) {
        if(s.empty()) return {};
        vector<int> res;
        int start = 1, cur = 1;
        for(int i = 0; i < s.size(); ++i){
            if(s[i] == 'I'){
                int tmp = cur;
                while(tmp >= start){
                    res.push_back(tmp--);
                }
                start = cur+1;
            }
            cur++;
        }
        while(start <= cur){
            res.push_back(cur--);
        }
        return res;
    }
    };
    

    Use Stack:

        class Solution {
        public:
        vector<int> findPermutation(string s) {
        if(s.empty()) return {};
        vector<int> res;
        stack<int> sk;
        int number = 1;
        for(int i = 0; i < s.size(); i++){
            if(s[i] == 'I'){
                sk.push(number);
                while(!sk.empty()){
                    res.push_back(sk.top());
                    sk.pop();
                }
            }else{
                sk.push(number);
            }
            number++;
        }
        sk.push(number);
        while(!sk.empty()){
            res.push_back(sk.top());
            sk.pop();
        }
        return res;
    }
    };

Log in to reply
 

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