Question

484. Find Permutation

中文文档

Description

A permutation perm of n integers of all the integers in the range [1, n] can be represented as a string s of length n - 1 where:

• s[i] == 'I' if perm[i] < perm[i + 1], and
• s[i] == 'D' if perm[i] > perm[i + 1].

Given a string s, reconstruct the lexicographically smallest permutation perm and return it.

 

Example 1:

Input: s = "I"
Output: [1,2]
Explanation: [1,2] is the only legal permutation that can represented by s, where the number 1 and 2 construct an increasing relationship.

Example 2:

Input: s = "DI"
Output: [2,1,3]
Explanation: Both [2,1,3] and [3,1,2] can be represented as "DI", but since we want to find the smallest lexicographical permutation, you should return [2,1,3]

 

Constraints:

• 1 <= s.length <= 105
• s[i] is either 'I' or 'D'.

Solutions

Solution 1

class Solution:
  def findPermutation(self, s: str) -> List[int]:
    n = len(s)
    ans = list(range(1, n + 2))
    i = 0
    while i < n:
      j = i
      while j < n and s[j] == 'D':
        j += 1
      ans[i : j + 1] = ans[i : j + 1][::-1]
      i = max(i + 1, j)
    return ans

class Solution {
  public int[] findPermutation(String s) {
    int n = s.length();
    int[] ans = new int[n + 1];
    for (int i = 0; i < n + 1; ++i) {
      ans[i] = i + 1;
    }
    int i = 0;
    while (i < n) {
      int j = i;
      while (j < n && s.charAt(j) == 'D') {
        ++j;
      }
      reverse(ans, i, j);
      i = Math.max(i + 1, j);
    }
    return ans;
  }

  private void reverse(int[] arr, int i, int j) {
    for (; i < j; ++i, --j) {
      int t = arr[i];
      arr[i] = arr[j];
      arr[j] = t;
    }
  }
}

class Solution {
public:
  vector<int> findPermutation(string s) {
    int n = s.size();
    vector<int> ans(n + 1);
    iota(ans.begin(), ans.end(), 1);
    int i = 0;
    while (i < n) {
      int j = i;
      while (j < n && s[j] == 'D') {
        ++j;
      }
      reverse(ans.begin() + i, ans.begin() + j + 1);
      i = max(i + 1, j);
    }
    return ans;
  }
};

func findPermutation(s string) []int {
  n := len(s)
  ans := make([]int, n+1)
  for i := range ans {
    ans[i] = i + 1
  }
  i := 0
  for i < n {
    j := i
    for ; j < n && s[j] == 'D'; j++ {
    }
    reverse(ans, i, j)
    i = max(i+1, j)
  }
  return ans
}

func reverse(arr []int, i, j int) {
  for ; i < j; i, j = i+1, j-1 {
    arr[i], arr[j] = arr[j], arr[i]
  }
}