DI String Match Problem & Solution
A permutation perm of n + 1 integers of all the integers in the range [0, n] can be represented as a string s of length n where:
s[i] == 'I'ifperm[i] < perm[i + 1], ands[i] == 'D'ifperm[i] > perm[i + 1].
Given a string s, reconstruct the permutation perm and return it.
If there are multiple valid permutations perm, return any of them.
See the DI string match problem on LeetCode.
C++ Solution
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")
static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();
class Solution {
public:
vector<int> diStringMatch(string s) {
int low = 0;
int high = s.size();
vector<int> result(s.size() + 1, 0);
for (int i = 0; i < s.size(); ++i) {
if (s[i] == 'I') {
result[i] = low++;
} else {
result[i] = high--;
}
}
result[s.size()] = low;
return result;
}
};