Consice 15-line C++ solution by using reverse

  • 1

    We initialize one vector from 1 to n and call it nums, so this should be the result if secret signature is made up with all I's.
    Imagine we meet one 'D' in the given secret signature, which means nums[i] should be smaller than nums[i+1], then all we need to do is swap nums[i] with nums[i+1].
    But what if we have multiple 'D' s?
    If we have continuous 'D's from s[i, j] then that means nums[i, j+1] should be in descending order, so we just reverse this subsequence in nums.
    By swiping from left to right, we are able to get the smallest permutation possible.
    Here is the code -

        vector<int> findPermutation(string s) 
            int n = s.length();
        	vector<int> nums(n + 1);
        	for (int i = 0; i < n + 1; i++) nums[i] = i+1; // initialize vector in increasing order
        	int i = 0;
        	while (i < n)
        		if (s[i] == 'I') i++;
        			int j = i; // remember the start point
        			while (i < n && s[i] == 'D') i++;
        			reverse(nums.begin()+j, nums.begin()+i+1); // affected range nums[j, i]
        	return nums;    

Log in to reply

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