Find Permutation - Tìm hoán vị nhỏ nhất theo thứ tự từ điển từ chuỗi D/I

Cho một chuỗi ký tự chỉ chứa 'D' (giảm) và 'I' (tăng). Chuỗi này được xây dựng từ một mảng nguyên đặc biệt chứa các số từ 1 đến n không trùng lặp. 'D' biểu thị quan hệ giảm giữa hai số liên tiếp, 'I' biểu thị quan hệ tăng.

Ví dụ: chuỗi "DI" có thể xây dựng từ mảng [2,1,3] hoặc [3,1,2], nhưng không thể từ [3,2,4] hoặc [2,1,3,4]. Yêu cầu: tìm hoán vị nhỏ nhất theo thứ tự từ điển của [1, 2, ..., n] thỏa mãn chuỗi ký tự.

Với "DI", kết quả là [2,1,3] vì nó nhỏ hơn [3,1,2] theo thứ tự từ điển.

Giải thuật (Sử dụng Stack)

Duyệt chuỗi, khi gặp 'D' đẩy chỉ số vào stack. Khi gặp 'I', đẩy chỉ số hiện tại vào kết quả, sau đó đẩy toàn bộ stack vào kết quả (đảo ngược đoạn giảm). Cuối cùng đẩy n+1 vào stack và đổ ra kết quả.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<int> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << ", ";
    }
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> findPermutation(string s) {
        stack<int> st;
        vector<int> ret;
        for (int i = 1; i <= s.size(); i++) {
            if (s[i - 1] == 'D') {
                st.push(i);
            } else {
                ret.push_back(i);
                while (!st.empty()) {
                    ret.push_back(st.top());
                    st.pop();
                }
            }
        }
        st.push(s.size() + 1);
        while (!st.empty()) {
            ret.push_back(st.top());
            st.pop();
        }
        return ret;
    }
};

int main() {
    Solution ob;
    print_vector(ob.findPermutation("DIID"));
    return 0;
}

Đầu vào

"DIID"

Đầu ra

[2, 1, 3, 5, 4, ]