Java one pass O(n) solution


  • 1
    public class Solution {
        public int[] findPermutation(String s) {
            if (s == null) return new int[0];
            int n = s.length();
            int[] result = new int[n + 1];
            int i = 0, a = 1, p = 0;
            
            while (i < n) {
                if (s.charAt(i) == 'I') {
            	result[p++] = a;
            	a++; i++;
                }
                else {
            	int j = i;
            	while (j < n && s.charAt(j) == 'D') j++;
            	int b = a + j - i;
            	for (; b >= a; b--) {
            	    result[p++] = b;
            	}
            	a = a + j - i + 1;
            	i = j + 1;
                }
            }
            
            if (p == n) result[p] = n + 1;
            
            return result;
        }
    }
    

Log in to reply
 

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