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], ands[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 <= 105s[i] is either 'I' or 'D'.
Solutions
Solution 1
PythonJavaC++Go
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(code-box)
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;
}
}
}(code-box)
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;
}
};(code-box)
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]
}
}(code-box)
