Straightforward Java O(n) Solution with Explanation


  • 1
    public class Solution {
        public int[] findPermutation(String s) {
            s = "I" + s;
            int[] res = new int[s.length()];
            for(int i = 0; i<res.length; i++) res[i] = i+1; 
            int lastI = 0; 
            for(int i = 1; i<=s.length(); i++){
                if(i==s.length() || s.charAt(i)=='I'){//check if we meet an I, or we reach the end
                    if(i-lastI > 1)  reverse(res, lastI, i-1);//skill case like "II" 
                    lastI = i;
                }
            }
            return res; 
        }
        
        private void reverse(int[] nums, int s, int e){
            while(s<e){
                int tmp = nums[s];
                nums[s] = nums[e];
                nums[e] = tmp;
                s++; e--;
            }
        }
    }
    

    As "DDIDIIDDD" is equivalent to "IDDIDIIDDD", we add an 'I' to the front of s to match our nums array, making it clearer.
    For a s = "DDIDIIDDD", init nums as [1,2,3,4,5,6,7,8,9,10]
    Then reverse all ID... sequences you can find.

    [1,2,3,4,5,6,7,8,9,10]
    [3,2,1,4,5,6,7,8,9,10]
    [3,2,1,5,4,6,7,8,9,10]
    [3,2,1,5,4,6,10,9,8,7], which is the answer


Log in to reply
 

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