Java O(n) clean solution easy to understand


  • 35
    Y

    For example, given IDIIDD we start with sorted sequence 1234567
    Then for each k continuous D starting at index i we need to reverse [i, i+k] portion of the sorted sequence.

    IDIIDD
    1234567 // sorted
    1324765 // answer
    
        public int[] findPermutation(String s) {
            int n = s.length(), arr[] = new int[n + 1]; 
            for (int i = 0; i <= n; i++) arr[i] = i + 1; // sorted
            for (int h = 0; h < n; h++) {
                if (s.charAt(h) == 'D') {
                    int l = h;
                    while (h < n && s.charAt(h) == 'D') h++;
                    reverse(arr, l, h); 
                }   
            }   
            return arr;
        }   
    
        void reverse(int[] arr, int l, int h) {
            while (l < h) {
                arr[l] ^= arr[h];
                arr[h] ^= arr[l];
                arr[l] ^= arr[h];
                l++; h--;
            }   
        }
    

  • 0
    T

    The range you given in your description should have k as an offset (i+k), not as an absolute position.


  • 0
    Y

    @TWiStErRob Yeah, my bad, I was thinking of length. Thanks.


  • 0

    similar here but you can avoid back counting loop if you just keep track of the current count of 'D' and you can initialize the array during same pass, no need to fill out he array ahead of time.

        public int[] FindPermutation(string s) 
        {
            int[] arr = new int[s.Length + 1];
            arr[0] = 1;
            int decreaseCnt = 0;
            for (int i = 0; i < s.Length; i++, decreaseCnt++)
            {
                arr[i+1] = i + 2;
                if (s[i] == 'I')
                {
                    Reverse(arr, i - decreaseCnt, i);
                    decreaseCnt = -1;
                }
            }
            
            Reverse(arr, arr.Length - 1 - decreaseCnt, arr.Length - 1);
            return arr;
        }
        
        public void Reverse(int[] arr, int i, int j)
        {
            int temp = 0;
            for (; i < j; i++, j--) 
            {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    

  • 0
    C

    Thanks for sharing, very clear explanation.


  • 0
    S

    brilliant idea! I was working on heavy backtracking method and of course I got a TLE. Thanks for the idea, and I like the xor way to swap elements inside an array. Thanks


  • 2
        public int[] findPermutation(String s) {
          int n = s.length();
          int[] res = new int[n + 1];
          for(int i = 0; i < res.length; i++) res[i] = i + 1;
          char[] sc = s.toCharArray();
          for(int i = 0; i < n; i++){
            if(sc[i] == 'D'){
              int start = i;
              while(i < n && sc[i] == 'D') i++;
              reverse(res, start, i);
            }
          }
          return res;
        }
        
        void reverse(int[] res, int start, int end){
          while(start < end){
            int temp = res[start];
            res[start]  = res[end];
            res[end] = temp;
            start++;
            end--;
          }    
        }

  • 0
    J
    This post is deleted!

  • 0
    X

    Here is the solution without reverse:

    public int[] findPermutation(String s) {
        final int[] res = IntStream.rangeClosed(1, s.length() + 1).toArray();
        for (int i = 0, len = s.length(); i < len;) {
            int j = i;
            while (j < len && s.charAt(j) == 'D') {
                j++;
            }
            for (int k = j - i; k >= 0; k--, j--) {
                res[i++] = j + 1;
            }
        }
        return res;
    }
    

  • 1

    @yuxiangmusic said in Java O(n) clean solution easy to understand:

    For example, given IDIIDD we start with sorted sequence 1234567
    Then for each k continuous D starting at index i we need to reverse [i, i+k] portion of the sorted sequence.

    IDIIDD
    1234567 // sorted
    1324765 // answer
    
        public int[] findPermutation(String s) {
            int n = s.length(), arr[] = new int[n + 1]; 
            for (int i = 0; i <= n; i++) arr[i] = i + 1; // sorted
            for (int h = 0; h < n; h++) {
                if (s.charAt(h) == 'D') {
                    int l = h;
                    while (h < n && s.charAt(h) == 'D') h++;
                    reverse(arr, l, h); 
                }   
            }   
            return arr;
        }   
    
        void reverse(int[] arr, int l, int h) {
            while (l < h) {
                arr[l] ^= arr[h];
                arr[h] ^= arr[l];
                arr[l] ^= arr[h];
                l++; h--;
            }   
        }
    

    Nice solution!
    Mark the next h position with nextH

    for (int h = 0; h < n; h++) {
                if (s.charAt(h) == 'D') {
                    int l = h;
                    while (h < n && s.charAt(h) == 'D') h++;
                    int nextH = h;
                    reverse(arr, l, h);
                    h = nextH;
                }
    }
    

    which reduces half of h backtracking, useful when the continuous h is large


  • 0
    H

    how did you come up with such a genius idea?


  • 0
    T

    Thank you for your method!

    class Solution {
        public int[] findPermutation(String s) {
            int[] array = new int[s.length()+1];
            for(int i=0;i<array.length;i++){
                array[i]=i+1;
            }
            
            for(int i=0;i<s.length();i++){
                if(s.charAt(i)=='D'){
                    int h=i;
                    while(h<s.length()&&s.charAt(h)=='D'){
                        h++;
                    }
                    reverse(array,i,h);
                    i=h;
                }
            }
            
            return array;
        }
        
        public void reverse(int[] array,int left,int right){
              while(left<right){
                  int t = array[left];
                  array[left] = array[right];
                  array[right] = t;
                  left++;
                  right--;
              }
        }
    }
    

  • 0
    G

    Brilliant idea!

    Here's my C++ version using STL methods.

    class Solution {
    public:
        vector<int> findPermutation(string s) {
            int n = (int)s.length() + 1;
            vector<int> nums(n);
            for (int i = 1; i <= n; ++i) nums[i - 1] = i;
            for (int l = 0, h = 0; l < n - 1; l = h + 1) {
                for (h = l; h < n - 1 && s[h] == 'D'; ++h);
                reverse(nums.begin() + l, nums.begin() + h + 1);
            }
            return nums;
        }
    };
    

Log in to reply
 

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