# 484. Find Permutation

By now, you are given a secret signature consisting of character ‘D’ and ‘I’. ‘D’ represents a decreasing relationship between two numbers, ‘I’ represents an increasing relationship between two numbers. And our secret signaturewas constructed by a special integer array, which contains uniquely all the different number from 1 to n (n is the length of the secret signature plus 1). For example, the secret signature “DI” can be constructed by array [2,1,3] or [3,1,2], but won’t be constructed by array [3,2,4] or [2,1,3,4], which are both illegal constructing special string that can’t represent the “DI” secret signature.

On the other hand, now your job is to find the lexicographically smallest permutation of [1, 2, … n] could refer to the given secret signature in the input.

Example 1:

``````Input: "I"
Output: [1,2]
Explanation: [1,2] is the only legal initial spectial string can construct secret signature "I", where the number 1 and 2 construct an increasing relationship.
``````

Example 2:

``````Input: "DI"
Output: [2,1,3]
Explanation: Both [2,1,3] and [3,1,2] can construct the secret signature "DI",
but since we want to find the one with the smallest lexicographical permutation, you need to output [2,1,3]
``````

Note:

• The input string will only contain the character ‘D’ and ‘I’.
• The length of input string is a positive integer and will not exceed 10,000

D D I I D I

1 2 3 4 5 6 7

3 2 1 4 6 5 7

``````class Solution {
public:
vector<int> findPermutation(string s) {
int n = s.size();
vector<int> res(n + 1);
for (int i = 0; i < n + 1; ++i) res[i] = i + 1;
for (int i = 0; i < n; ++i) {
if (s[i] != 'D') continue;
int j = i;
while (s[i] == 'D' && i < n) ++i;
reverse(res.begin() + j, res.begin() + i + 1);
--i;
}
return res;
}
};
``````

``````class Solution {
public:
vector<int> findPermutation(string s) {
vector<int> res;
for (int i = 0; i < s.size() + 1; ++i) {
if (i == s.size() || s[i] == 'I') {
int size = res.size();
for (int j = i + 1; j > size; --j) {
res.push_back(j);
}
}
}
return res;
}
};
``````

Palindrome Permutation II

Palindrome Permutation

Permutation Sequence

Permutations II

Permutations

Next Permutation

https://leetcode.com/problems/find-permutation/

https://leetcode.com/problems/find-permutation/discuss/96644/c-simple-solution-in-72ms-and-9-lines

https://leetcode.com/problems/find-permutation/discuss/96663/greedy-on-java-solution-with-explanation

https://leetcode.com/problems/find-permutation/discuss/96613/java-on-clean-solution-easy-to-understand

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation