Leetcode 484. Find Permutation

We can reverse the range of ‘D’ as shown in the figure below.

Image from HERE
class Solution {
public:
vector<int> findPermutation(string s) {
const int n = s.length() + 1;
vector<int> ret(n);
for (int i = 1; i<= n; ++i)
{
ret[i-1] = i;
}
int left = 0, right = 0;
for (int i = 1; i < n; ++i)
{
if (s[i-1] == 'I')
{

if (i-2 >= 0 && s[i-2] == 'D')
{
reverse(ret.begin() + left, ret.begin() + i);
}
left = i;
}
else if (i == n-1 && s[i-1]=='D')
{
reverse(ret.begin() + left, ret.end());
}
}
return ret;
}
};
// IIII II(DD)
// 12345 12(345)
// IIIIII. II(DD)I(D)
// 1234567. 12(345)(67)

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi