484. Find Permutation

Description

Solution

Recall how to generate a next_permutation, the way we do to keep the permutation small is just reverse the left-most reverse pair. In this question, we just keep a ‘123456… n’ basic permutation then reverse the substr that contiguous ‘D’ point at.

eg.

Code

class Solution {
public:
    vector<int> findPermutation(string s) {
        int n = s.size() + 1;
        vector<int> res;
        for(int i = 1; i <= n; i++){
            res.push_back(i);
        }
        for(int i = 0; i < n-1; i++){
            if(s[i] == 'D'){
                int j;
                for(j = i + 1; j < n-1; j++){
                    if(s[j]== 'I') break;
                }
                //reverse from res[i] to res[j]
                reverse(res.begin() + i, res.begin() + j + 1);
                i = j;
            }
        }
        return res;
    }

};