C# - one pass, clean code


  • 0

    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

    We have essentially the same solution to reverse arrays where streak of 'D' is detected:

        vector<int> findPermutation(string s) {
          vector<int> res((s += 'I').size());
          for (int i = 0, j = 0; i < s.size() && (res[i] = ++i); )
            if (s[i-1] == 'I') reverse(res.begin()+j, res.begin()+i), j = i;
    
          return res;
        }
    

  • 0

    yep, your's is a bit more compact. Many others had the same as well.


Log in to reply
 

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