একটি প্যারেনথেসিস সিকোয়েন্স দেওয়া আছে; এখন, আপনাকে অবৈধ ব্র্যাকেটগুলো রিমুভ করে সেটি যে সব ভ্যালিড প্যারেনথেসিস বানাতে পারে সেগুলো প্রিন্ট করতে হবে। উদাহরণস্বরূপ:
Input : str = “()())()” - Output : ()()() (())() দুটি সম্ভাব্য সমাধান "()()()" এবং "(())()" Input : str = (v)())() Output : (v)()() (v())()
এই সমস্যায়, আমরা ব্যাকট্র্যাকিং (backtracking) ব্যবহার করব যাতে সেটি সব ভ্যালিড সিকোয়েন্স প্রিন্ট করে।
সমাধানের পদ্ধতি
এই পদ্ধতিতে, আমরা ওপেনিং এবং ক্লোজিং ব্র্যাকেটগুলো এক এক করে BFS ব্যবহার করে রিমুভ করার চেষ্টা করব। এখন প্রতিটি সিকোয়েন্সের জন্য চেক করব এটি ভ্যালিড কিনা। যদি ভ্যালিড হয়, তবে সেটি আউটপুট হিসেবে প্রিন্ট করব।
উদাহরণ
#include <bits/stdc++.h> using namespace std; bool isParenthesis(char c){ return ((c == '(') || (c == ')')); } bool validString(string str){ // cout << str << " "; int cnt = 0; for (int i = 0; i < str.length(); i++){ if (str[i] == '(') cnt++; else if (str[i] == ')') cnt--; if (cnt < 0) return false; } // cout << str << " "; return (cnt == 0); } void validParenthesesSequences(string str){ if (str.empty()) return ; set<string> visit; // যদি স্ট্রিং চেক করা হয় তবে ভিজিট-এ রাখি // যাতে আমরা সেই স্ট্রিং আবার এনকাউন্টার না করি queue<string> q; // BFS করার জন্য কিউ string temp; bool level; // দেওয়া স্ট্রিংকে স্টার্টিং নোড হিসেবে কিউতে পুশ করুন q.push(str); visit.insert(str); while (!q.empty()){ str = q.front(); q.pop(); if (validString(str)){ // cout << "s"; cout << str << "\n"; // আমরা আমাদের স্ট্রিং প্রিন্ট করি level = true; // যেহেতু আমরা একই লেভেলে স্ট্রিং পেলাম তাই এখন আর BFS প্রয়োগ করতে হবে না } if (level) continue; for (int i = 0; i < str.length(); i++){ if (!isParenthesis(str[i])) // আমরা ব্র্যাকেট ছাড়া অন্য ক্যারেক্টার রিমুভ করব না continue; temp = str.substr(0, i) + str.substr(i + 1); // স্ট্রিং থেকে এক এক করে প্যারেনথেসিস রিমুভ করুন if (visit.find(temp) == visit.end()) { // যদি স্ট্রিং চেক করা হয় তবে আবার চেক করব না q.push(temp); visit.insert(temp); } } } } int main(){ string s1; s1 = "(v)())()"; cout << "Input : " << s1 << "\n"; cout << "Output : "; validParenthesesSequences(s1); return 0; }
আউটপুট
Input : (v)())() Output : (v())()
উপরোক্ত কোডের ব্যাখ্যা
উপরের পদ্ধতিতে, আমরা সিম্পলি এক এক করে আমাদের প্যারেনথেসিস রিমুভ করি। এখন যেহেতু আমরা ব্র্যাকেট রিমুভ করি, আমরা আগের সিকোয়েন্সগুলোর ট্র্যাক রাখি যাতে আমরা একই সিকোয়েন্স দুবার চেক না করি। এখন যদি এই সব সম্ভাবনা থেকে কোনো ভ্যালিড সিকোয়েন্স পাই, তবে আমরা সব ভ্যালিড সম্ভাবনা প্রিন্ট করি এবং এভাবেই আমাদের প্রোগ্রাম এগিয়ে যায়।
উপসংহার
এই টিউটোরিয়ালে, আমরা ইনভ্যালিড প্যারেনথেসিস রিমুভ করার সমস্যা সমাধান করেছি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (সাধারণ) শিখেছি। একই প্রোগ্রামটি C, Java, Python এবং অন্যান্য ভাষায়ও লিখা যায়। আশা করি আপনি এই টিউটোরিয়ালটিকে উপকারী পাবেন।
