মডিউল ১৫-২ঃ Backspace String Compare (Leetcode)

প্রবলেম লিংকঃ Backspace String Compare - LeetCode

প্রবলেম স্টেটমেন্টঃ ইনপুটে দুটি স্ট্রিং থাকবে। এই দুটি স্ট্রিং যদি কোন টেক্সট এডিটরে টাইপ করা হয় তাহলে দুটি স্ট্রিং সেইম হবে কিনা। সেইম হলে ট্রু রিটার্ন করতে হবে। সেইম না হলে ফলস রিটার্ন করতে হবে। এক্ষেত্রে ইনপুটে # থাকা মানে বেকস্পেস বুঝায়। অর্থাৎ স্ট্রিংটি যদি হয় ab#cde#f তাহলে বেকস্পেস এর আগের ক্যারেক্টার গুলো সরিয়ে দিলে ফাইনাল স্ট্রিংটি হবে এরকম acdf. সল্যুশনঃ আমরা স্ট্যাক দিয়ে এটি খুব সহজেই সল্ভ করে ফেলতে পারি। স্ট্রিং এর সবগুলো ক্যারেক্টার স্ট্যাকে পুশ করতে থাকব। তারপর যখনি বেকস্পেস পাব অর্থাৎ # পাব তখন পপ করে দিব। তাহলে বেকস্পেস এর আগে থাকা ক্যারেক্টার স্ট্যাক থেকে পপ হয়ে যাবে। সেইম কাজ আমরা দুটি স্ট্রিং এর জন্যই করব। তারপর কম্পেয়ার করে দেখব দুটি স্ট্রিং সেইম কিনা। সেইম হলে ট্রু রিটার্ন করব আর নাহলে ফলস রিটার্ন করব।

class Solution
{
public:
    bool backspaceCompare(string s, string t)
    {
        stack<char> s1, s2;   
        for (char c : s)    // লুপ চালিয়ে স্ট্রিং এর প্রতিটি ক্যারেক্টারে যাওয়া হচ্ছে।
        {
            if (c == '#')    // যদি বেকস্পেস পাই তাহলে পপ করব।
            {
                if (!s1.empty())
                    s1.pop();
            }
            else      // বেকস্পেস ছাড়া অন্য কোন ক্যারেক্টার পেলে পুশ করে রেখে দিব। 
            {
                s1.push(c);
            }
        }
        for (char c : t)     // সেইম কাজ দ্বিতীয় স্ট্রিং এর ক্ষেত্রেও। 
        {
            if (c == '#')     // যদি বেকস্পেস পাই তাহলে পপ করব।
            {
                if (!s2.empty())
                    s2.pop();
            }
            else      // বেকস্পেস ছাড়া অন্য কোন ক্যারেক্টার পেলে পুশ করে রেখে দিব। 
            {
                s2.push(c);
            }
        }
        return s1 == s2;   // চেক করে দেখছি স্ট্রিং দুটি সমান কিনা। সমান হলে ট্রু রিটার্ন হবে নাহলে ফলস।
    }
};