Easy to understand Java solution with explanation


  • 1
    M

    Some notes:

    1. if the signature starts with "I", 1 must appear @ the beginning of array
    2. if the signature starts with "D", 1 must appear @ the end of array
    3. Then the idea is to reverse the portion of the array which corresponds to D's in signature, and since we reverse the array by the index of smallest element seen so far, it is lexicographically smallest permutation.
    
        public int[] findPermutation(String s) {
            if(s==null) return new int[]{};
            int n= s.length()+1;
     
            int[] res = new int[n];
            for(int i=1; i<=n; i++){
            	res[i-1]=i;
            }
            
            int lasti=0;
            for(int i=0; i<s.length(); i++){
            	if(s.charAt(i)=='I'){
            		reverse(res, lasti, i);
            		lasti=i+1;
            		
            	}
            }       
            reverse(res, lasti, s.length());
           
            return res;
        
        }
        
        public static void reverse(int[] res, int s, int e) {
    		// TODO Auto-generated method stub
        	
    		while(s<e){
    			swap(res, s, e);
    			s++;
    			e--;
    		}
    	}
        
        public static void swap(int[] nums, int a, int b){
    		int temp=nums[a];
    		nums[a] =nums[b];
    		nums[b] =temp;
    	}
    
    

Log in to reply
 

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