C++-এ স্ট্রিং ডিকোড করা

ধরা যাক আমাদের একটি এনকোড করা স্ট্রিং আছে; আমাদের এর ডিকোড করা স্ট্রিংটি ফেরত দিতে হবে। এনকোডিংয়ের নিয়ম হলো: k[encoded_string], এখানে স্কোয়ার ব্র্যাকেটের ভিতরের encoded_string সঠিকভাবে k বার রিপিট হবে। আমরা অনুমান করতে পারি যে মূল ডেটাতে কোনো 숫রিক ক্যারেক্টার নেই এবং ডিজিটগুলো শুধু রিপিট সংখ্যা k-এর জন্য ব্যবহৃত হয়। তাই যদি ইনপুট হয় "1[ba]2[na]", তবে আউটপুট হবে "banana"।

এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব:

• একটি খালি স্ট্যাক তৈরি করুন, i := 0 সেট করুন
• যখন i < স্ট্রিংয়ের আকার
  • যদি s[i] == ']' হয়
    • res := স্ট্যাক থেকে এলিমেন্ট ডিলিট করুন এবং স্কোয়ার ব্র্যাকেটের ভিতরের স্ট্রিংটি নিন
    • n := 0
    • যখন স্ট্যাক খালি না এবং স্ট্যাকের টপ একটি 숫রিক ক্যারেক্টার হয়, তখন সংখ্যাগুলো একত্রিত করে প্রকৃত ইন্টিজার n তৈরি করুন
    • j = 1 থেকে n পর্যন্ত
      • x = 0 থেকে res-এর আকার পর্যন্ত
        • res[x] স্ট্যাকে ইনসার্ট করুন
  • অন্যথায় s[i] স্ট্যাকে ইনসার্ট করুন
  • i 1 দিয়ে বৃদ্ধি করুন
• ans := একটি খালি স্ট্রিং
• যখন স্ট্যাক খালি না
  • ans := স্ট্যাকের টপ এলিমেন্ট + ans
  • স্ট্যাক থেকে পপ করুন
• ans রিটার্ন করুন

উদাহরণ (C++):

নিচের ইমপ্লিমেন্টেশনটি দেখে আরও ভালো বুঝতে পারবেন:

#include <bits/stdc++.h> using namespace std; class Solution { public:    string decodeString(string s) {       stack <char> st;       int i = 0;       while(i<s.size()){          if(s[i] == ']'){             string res = "";             while(st.top()!='['){                res = st.top() + res;                st.pop();             }             st.pop();             int n = 0;             int x = 1;             while(!st.empty() && st.top()>='0' && st.top()<='9'){                n = n + (st.top()-'0')*x;                x*=10;                st.pop();             }             for(int j = 1; j <= n; j++){                for(int x = 0; x < res.size();x++){                   st.push(res[x]);                }             }          }          else{             st.push(s[i]);          }          i++;       }       string ans ="";       while(!st.empty()){          ans = st.top() + ans;          st.pop();       }       return ans;    } }; main(){    Solution ob;    cout << ob.decodeString("1[ba]2[na]"); }

ইনপুট

"1[ba]2[na]"

আউটপুট

"banana"