JAVA 7ms one pass solution with details. Reverse part of the list


  • 0

    The idea to find out the permutation is like following:

    we take 1,2,3,4,5 as example.

    if assuming we have the array 12345 at beginning, then for these situations:

    IIII: 12345
    DDDD: 54321
    DIDI: 21435
    IIDD: 12543

    As you can see here, they can all be generated by 12345, if we meet 'I', we do nothing. If we meet 'D', we reverse the subarray which has the length: number of D + 1.

    Here comes the code:

    public int[] findPermutation(String s) {
        int[] res = new int[s.length()+1];
        for (int i = 0; i < res.length; i++) res[i] = i+1;
        int start = -1, count = 0;
        for (int i = 0; i < s.length(); i++){
            if (s.charAt(i) == 'I'){
                if (start != -1) {
                    reverse(res, start, count);
                    start = -1;
                    count = 0;
                }
            }
            else {
                if (start == -1) start = i;
                count++;
            }
        }
        if (start != -1) reverse(res, start, count);
        
        return res;
    }
    private void reverse(int[] res, int lo, int len) {
        int hi = lo + len;
        while(lo < hi) {
            int temp = res[lo];
            res[lo] = res[hi];
            res[hi] = temp;
            lo++; hi--;
        }
    }

Log in to reply
 

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