মডিউল ১৫-১ঃ Valid Parentheses (Leetcode)

প্রবলেম লিংকঃ Valid Parentheses - LeetCode

প্রবলেম স্টেটমেন্টঃ ইনপুটে একটি স্ট্রিং থাকবে, যাতে শুধুমাত্র ব্র্যাকেট থাকবে। আপনাকে চেক করে বলতে হবে স্ট্রিং এর ব্র্যাকেট গুলো ভ্যালিড কিনা।

স্ট্রিং ভেলিড হওয়ার তিনটি শর্তঃ

১। ওপেনিং ব্র্যাকেটকে অবশ্যই সেইম টাইপের ক্লোজিং ব্যাকেট দিয়ে বন্ধ করতে হবে।

২। ওপেনিং ব্র্যাকেটের অর্ডার অনুযায়ী ক্লোজিং ব্র্যাকেট থাকতে হবে।

৩। একটি ক্লোজিং ব্র্যাকেটের জন্য তার আগে অবশ্যই সেইম টাইপের একটি ওপেনিং ব্র্যাকেট থাকতে হবে। সল্যুশনঃ আমরা যখনি কোন ওপেন ব্র্যাকেট (, {, [ পাব তখনি সেটি একটি স্ট্যাকে পুশ করে রেখে দিব। আর যখনি কোন ক্লোজিং ব্র্যাকেট ), }, ] পাব তখন চেক করে দেখব স্ট্যাকের টপে সেই টাইপের ওপেন ব্র্যাকেট আছে কিনা। যদি থাকে তাহলে আমাদের ব্র্যাকেটের অর্ডার ঠিক আছে। তখন আমরা পপ করে দিচ্ছি। আর যদি স্ট্যাকের টপে সেই টাইপের ওপেন ব্র্যাকেট না থাকে তাহলে ব্র্যাকেটের অর্ডার ঠিক নেই, রিটার্ন ফলস করে দিতে পারি।

class Solution
{
public:
    bool isValid(string s)
    {
        stack<char> st;
        for (char c : s)
        {
            if (c == '(' || c == '{' || c == '[')    // আমরা যখনি কোন ওপেন ব্র্যাকেট (, {, [ পাব তখনি সেটি একটি স্ট্যাকে পুশ করে রেখে দিব
            {
                st.push(c);
            }
            else            //  আর যখনি কোন ক্লোজিং ব্র্যাকেট ), }, ] পাব
            {
                if (st.empty())
                {
                    return false;
                }
                else           // তখন চেক করে দেখব স্ট্যাকের টপে সেই টাইপের ওপেন ব্র্যাকেট আছে কিনা।
                {
                    if (c == ')' && st.top() == '(')
                    {
                        st.pop();     //  যদি থাকে তাহলে আমাদের ব্র্যাকেটের অর্ডার ঠিক আছে। তখন আমরা পপ করে দিচ্ছি।
                    }
                    else if (c == '}' && st.top() == '{')
                    {
                        st.pop();
                    }
                    else if (c == ']' && st.top() == '[')
                    {
                        st.pop();
                    }
                    else
                    {
                        return false;      // আর যদি স্ট্যাকের টপে সেই টাইপের ওপেন ব্র্যাকেট না থাকে তাহলে ব্র্যাকেটের অর্ডার ঠিক নেই, রিটার্ন ফলস করে দিতে পারি। 
                    }
                }
            }
        }
        return st.empty();
    }
};