O(n) solution in Java (7-9 ms)


  • 0
    D

    The code I wrote during the contest unfortunately did not generate correct results, but I kept working on it. I submitted it multiple times to see the runtime; first few times it was 7 ms, last time it was 9 ms.

    It searches for 'I's in the signature in reverse order. Whenever an 'I' is found, the maximum possible number is assigned to it. If there are any 'D's following that 'I' in the signature, they are assigned the max possible number until another 'I' (that has been processed previously) is found.

    public class Solution {
        public int[] findPermutation(String s) {
        	int i, j;
        	int prevI = -1;
        	int upper;
        	
        	if (s == null) return new int[0];
        	if (s.length() == 0) return new int[0];
        	
        	int n = s.length() + 1;
        	int[] r = new int[n];
        	
            for (i = s.length() - 1; i >=0; i--)
            	if (s.charAt(i) == 'I')
            	{
            		r[i+1] = n--;
            		upper = (prevI == -1) ? r.length - 1 : prevI;
            		for (j = i+2; j <= upper; j++)
            			r[j] = n--;
            		prevI = i;
            	}
            
            if (s.charAt(0) == 'D')
            	while(n > 0)
            		r[++i] = n--;
            else r[0] = n;
            
            return r;
        }
    }
    

Log in to reply
 

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