C++ में परम्यूटेशन खोजें - गुप्त हस्ताक्षर से लेक्सिकोग्राफिकली सबसे छोटा

समस्या विवरण

मान लीजिए हमारे पास एक गुप्त हस्ताक्षर है जिसमें वर्ण 'D' और 'I' होते हैं। 'D' दो संख्याओं के बीच घटते संबंध को दर्शाता है, 'I' बढ़ते संबंध को दर्शाता है। यह गुप्त हस्ताक्षर एक विशेष पूर्णांक सरणी द्वारा निर्मित किया गया था, जिसमें 1 से n तक सभी अलग-अलग संख्याएं विशिष्ट रूप से होती हैं।

उदाहरण के लिए, गुप्त हस्ताक्षर "DI" को [2,1,3] या [3,1,2] जैसी सरणी से बनाया जा सकता है, लेकिन [3,2,4] या [2,1,3,4] जैसी सरणी से नहीं, जो दोनों अवैध हैं और "DI" गुप्त हस्ताक्षर का प्रतिनिधित्व नहीं कर सकते।

अब हमें [1, 2, ... n] का लेक्सिकोग्राफिकली सबसे छोटा परम्यूटेशन ढूंढना है जो दिए गए गुप्त हस्ताक्षर को संदर्भित कर सके।

यदि इनपुट "DI" है, तो आउटपुट [2,1,3] होगा। जैसा कि हम जानते हैं [3,1,2] भी "DI" गुप्त हस्ताक्षर का निर्माण कर सकता है, लेकिन चूंकि हमें सबसे छोटे लेक्सिकोग्राफिकल परम्यूटेशन को ढूंढना है, हमें [2,1,3] आउटपुट करना होगा।

समाधान दृष्टिकोण

स्टैक-आधारित दृष्टिकोण का उपयोग करके:

1. एक स्टैक (st) परिभाषित करें
2. cnt := 2
3. एक सरणी ret परिभाषित करें
4. i को 1 से s के आकार तक लूप करें:
   • यदि s[i-1] == 'D', तो i को st में डालें
   • अन्यथा:
     • i को ret के अंत में डालें
     • जब तक st खाली न हो:
       • st के शीर्ष तत्व को ret के अंत में डालें
       • st से तत्व हटाएं
5. s के आकार को st में डालें
6. जब तक st खाली न हो:
   • st के शीर्ष तत्व को ret के अंत में डालें
   • st से तत्व हटाएं
7. ret लौटाएं

C++ कार्यान्वयन

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

void print_vector(vector<auto> 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; 
        int cnt = 2; 
        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;
}

इनपुट

"DIID"

आउटपुट

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