A weird but concise java O(n) solution


  • 0
    S
        public int[] findPermutation(String s) {
            int len = s.length();
            int[] ans = new int[len+1];
            
            int i =0, end = 0;
            
            while (end < len && s.charAt(end) == 'D') {
                end++;
            }
            for (i = 0; i <= end; i++) {
                ans[i] = end + 1 - i;
            }
            int cur = end+2, index = end+1;
            while (end < len) {
                int inc = 0;
                while (end < len && s.charAt(end) == 'I') {
                    end++;
                    inc++;
                }
                int dec = 0;
                while (end < len && s.charAt(end) == 'D') {
                    end++;
                    dec++;
                }
                for (i=0;i<inc-1;i++) {
                    ans[index++] = cur++;
                }
                int peak = index++;
                for (i=dec-1;i>= 0;i--) {
                    ans[index + i] = cur++;
                }
                index += dec;
                ans[peak] = cur++;
            }
            
            return ans;
        }
    }

Log in to reply
 

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