c++ solution , worst case O(n^2)


  • 0
    J

    Idea: in one sweep, when meet 'D', swap elements in the current "D...D" sequence.

    Example:
    input : s = "DDIIDI"
    output: nums = {2,1,3,4,6,5,7}

    original sequence: nums = {1,2,3,4,5,6,7}
    s[0] = D:swap nums[0] and nums[1] --> nums = {2,1,3,4,5,6,7}
    s[1] = D: swap nums[2] and nums[1], then swap nums[1] and nums[0] --> nums = {3,2,1,4,5,6,7}
    s[2] = I: nothing to do
    s[3] = I: nothing to do
    s[4] = D: swap nums[5] and nums[4] --> nums = {3,2,1,4,6,5,7}
    s[5] = I: nothing to do

    class Solution {
    public:
        vector<int> findPermutation(string s) {
            int len = s.length();
            vector<int> ret(len+1, 0);
            for(int i = 0; i < len+1; i++){
                ret[i] = i+1;
            }
            for(int i = 0; i< len; i++){
                if(s[i]=='D'){
                    int j = i;
                    while(j>=0 && s[j]=='D'){
                        swap(ret[j+1], ret[j]);
                        j--;
                    }
                }
            }
            return ret;
        }
    };
    

Log in to reply
 

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