চেক প্যালিনড্রোম (Palindrome) - using Stack

 

আমি বেশ কিছুদিন আগে Stack এবং Queue ডাটা-স্ট্রাকচার নিয়ে আলোচনা করেছিলাম সাথে জাভাস্ক্রিপ্ট এবং পাইথন দিয়ে ইমপ্লিমেন্টও করেছিলাম । তো আজকে আমি, একটি সুপরিচিত এবং সহজ প্রব্লেম নিয়ে আলোচনা করবো এবং Stack ডাটা-স্ট্রাকচার দিয়ে সমাধান করবো ।

আমরা জানি, Stack ডাটা-স্ট্রাকচার LIFO(Last In First Out) প্যারাডাইম মেনে চলে অর্থাৎ এখানে কোনো ভ্যালু শেষে এড করা হলে তা প্রথমে ডিলিট হয়ে যাবে । আপনি যদি Stack ও Queue ডাটা-স্ট্রাকচার সম্পর্কে না জেনে থাকেন তাহলে নিচের দেওয়া লিঙ্কগুলো থেকে পরে নিতে পারেন -

• Stack ডাটা-স্ট্রাকচার ইন জাভাস্ক্রিপ্ট
• Queue ডাটা-স্ট্রাকচার ইন জাভাস্ক্রিপ্ট
• Stack ডাটা-স্ট্রাকচার ইন পাইথন
• Queue ডাটা-স্ট্রাকচার ইন পাইথন

এখন, আসল কাজে ফিরে আসা যাক - আপনাকে একটি ফাংশন লিখতে হবে যা প্যারামিটার হিসেবে একটি স্ট্রিং নিবে । যদি স্ট্রিং টি Palindrome হয় তাহলে true নতুবা false রিটার্ন করবে ।

Palindrome String :-

যদি কোনো স্ট্রিং ডানে এবং বামে অর্থাৎ উভয় থেকে একই হয় তাহলে তাকে Palindrome String বলা যায় । যেমন :- mam, madam, racecar ইত্যাদি ।

এখন এই প্রব্লেমটি আমরা অনেক ভাবেই সমাধান করতে পারি আবার এক লাইনেও সমাধান করতে পারি । কিন্তু আমরা অন্যভাবে প্রব্লেমটি সমাধান না করে Stack দিয়ে কিভাবে সমাধান করতে হয় তা দেখবো এবং বোঝার চেষ্টা করবো ।

ধরি, আমাদের কাছে একটি স্ট্রিং আছে "MaM" । আমরা চাইলে সরাসরি Stack ডাটা-স্ট্রাকচার ইমপ্লিমেন্ট করে তা দিয়ে সমাধান করতে পারি । কিন্তু, Stack ডাটা-স্ট্রাকচার সরাসরি ইমপ্লিমেন্ট না করেও জাভাস্ক্রিপ্টের অ্যারে অথবা পাইথনের লিস্ট দিয়ে খুব সহজেই Stack এর কাজ করে ফেলতে পারি তো চলুন শুরু করা যাক -

স্টেপ(০১) :- প্রথমে, "MaM" স্ট্রিং এর প্রত্যেকতা উপাদানকে একটি অ্যারে বা লিস্টে রাখতে হবে । সেক্ষেত্রে, আমাদের একটি ফাকা লিস্ট বা অ্যারে নিতে হবে -

contains = []

এরপর, স্ট্রিং এর প্রথম উপাদান "M" কে contains নামের অ্যারে বা লিস্টে এ পুশ করে দেই । এক্ষেত্রে, কিন্তু "M" উপাদানকে contains নামের অ্যারের শেষে রাখলাম । এখন অ্যারেটি যদি দেখি -

contains = ["M"]

স্টেপ(০২) :- এখন স্ট্রিং এর দ্বিতীয় উপাদান অর্থাৎ "a" কে contains নামের অ্যারে বা লিস্টে পুশ করে দেই । আবারও বলি পুশ করা মানে কিন্তু উপাদানকে অ্যারের শেষে যুক্ত করা এখন অ্যারেটি যদি আবার দেখি -

contains = ["M", "a"]

স্টেপ(০৩) :- স্ট্রিং এর শেষ উপাদান অর্থাৎ "M" কে contains নামের অ্যারে বা লিস্টে পুশ করে দিলাম -

contains = ["M", "a", "M"]

এখন লিস্ট বা অ্যারে থেকে প্রত্যেকটা উপাদান pop() করবো । pop() মানে হলো যে উপাদানটি আমরা সবার শেষে এড করেছি সেই উপাদান এখন সবার প্রথমে রিমুভ করে অন্য স্ট্রিং এ রাখবো । তারপর ফাংশনে প্যারামিটার হিসেবে পাওয়া স্ট্রিং এর সাথে তুলনা করে দেখবো যে স্ট্রিং টি Palindrome কি না ।

একটা ফাকা স্ট্রিং নিলাম word নামে - 

word = ""

এখন contains অ্যারে থেকে শেষের ভ্যালুকে রিমুভ অর্থাৎ pop() করে word স্ট্রিং এর মধ্যে রাখলাম । এখন contains অ্যারে হবে ২ উপাদান বিশিষ্ট এবং word স্ট্রিং টি হবে ১ উপাদান বিশিষ্ট -

word = "M" 

contains = ["M", "a"]

আবার, contains অ্যারে থেকে শেষের ভ্যালু রিমুভ অর্থাৎ pop() করে word এর মধ্যে রাখলাম -

word = "Ma" 

contains = ["M"]

এখন,  contains অ্যারে তে একটি মাত্র উপাদানই আছে সেইটাকেও রিমুভ অর্থাৎ pop() করে word এর মধ্যে রাখলাম -

word = "MaM" 

contains = []

এই word হলো আমাদের নতুন স্ট্রিং, এখন এই word এর সাথে function এর প্যারামিটার তুলনা করবো যদি দুইটা সমান হয় তাহলে true নতুবা false রিটার্ন করবে ।

যেহেতু, আমাদের প্যারামিটার এবং word এর মান একই সেহেতু "MaM" একটি Palindrome স্ট্রিং ।

আরেকটি উদাহরণ :-

ধরি আমাদের কাছে একটি str নামে স্ট্রিং আছে,

 str = "abc" ।

স্টেপ(০১) :- প্রথমে, "abc" স্ট্রিং এর প্রত্যেকতা উপাদানকে একটি অ্যারে বা লিস্টে রাখতে হবে । সেক্ষেত্রে, আমাদের একটি ফাকা লিস্ট বা অ্যারে নিতে হবে -

contains = []

এরপর, স্ট্রিং এর প্রথম উপাদান "a" কে contains নামের অ্যারে বা লিস্টে এ পুশ করে দেই । এক্ষেত্রে, কিন্তু "a" উপাদানকে contains নামের অ্যারের শেষে রাখলাম । এখন অ্যারেটি যদি দেখি -

contains = ["a"]

স্টেপ(০২) :- এখন স্ট্রিং এর দ্বিতীয় উপাদান অর্থাৎ "b" কে contains নামের অ্যারে বা লিস্টে পুশ করে দেই । আবারও বলি পুশ করা মানে কিন্তু উপাদানকে অ্যারের শেষে যুক্ত করা এখন অ্যারেটি যদি আবার দেখি -

contains = ["a", "b"]

স্টেপ(০৩) :- স্ট্রিং এর শেষ উপাদান অর্থাৎ "c" কে contains নামের অ্যারে বা লিস্টে পুশ করে দিলাম -

contains = ["a", "b", "c"]

এখন লিস্ট বা অ্যারে থেকে প্রত্যেকটা উপাদান pop() করবো । pop() মানে হলো, যে উপাদানটি আমরা সবার শেষে এড করেছি সেই উপাদান এখন সবার প্রথমে রিমুভ করে অন্য স্ট্রিং এ রাখবো । তারপর ফাংশনে প্যারামিটার হিসেবে পাওয়া স্ট্রিং এর সাথে তুলনা করে দেখবো যে স্ট্রিং টি Palindrome কি না ।

একটা ফাকা স্ট্রিং নিলাম word নামে - 

word = ""

এখন contains অ্যারে থেকে শেষের ভ্যালুকে রিমুভ অর্থাৎ pop() করে word স্ট্রিং এর মধ্যে রাখলাম । এখন contains অ্যারে হবে ২ উপাদান বিশিষ্ট এবং word স্ট্রিং টি হবে ১ উপাদান বিশিষ্ট -

word = "c" 

contains = ["a", "b"]

আবার, contains অ্যারে থেকে শেষের ভ্যালু রিমুভ অর্থাৎ pop() করে word এর মধ্যে রাখলাম -

word = "cb" 

contains = ["a"]

এখন, contains অ্যারে তে একটি মাত্র উপাদানই আছে সেইটাকেও রিমুভ অর্থাৎ pop() করে word এর মধ্যে রাখলাম -

word = "cba" 

contains = []

এই word হলো আমাদের নতুন স্ট্রিং, এখন এই word এর সাথে function এর প্যারামিটার তুলনা করবো যদি দুইটা সমান হয় তাহলে true নতুবা false রিটার্ন করবে ।

যেহেতু, আমাদের প্যারামিটার ছিলো "abc" এবং word এর মান "cba" সেহেতু "abc" একটি Palindrome স্ট্রিং নয়।

তো চলুন এখন কোড লিখা যাক -

জাভাস্ক্রিপ্টে ইমপ্লিমেন্টেশন -

const isPalindrome = (str) => {
  let contains = [];
  for (let i = 0; i < str.length; i++) {
    contains.push(str[i]);
  }

  let word = "";
  while (contains.length > 0) {
    word += contains.pop();
  }
  return word === str;
};

Output :

isPalindrome("MaM");  // true
isPalindrome("abc"); // false

পাইথনে ইমপ্লিমেন্টেশন :-

def isPalindrome(str):
    contains = []
    for item in str:
        contains.append(item)

    word = ""
    while len(contains) > 0:
        word += contains.pop()

    return word == str

Output :

isPalindrome("MaM"); # True
isPalindrome("abc"); # False

কোড বিশ্লেষণ :-

উপরোক্ত কোডে, প্রথমে contains নামে একটি অ্যারে বা লিস্ট নিয়েছি । তারপর, স্ট্রিং এ লুপ থ্রু করেছি এবং প্রত্যেকতা উপাদানকে contains নামের অ্যারে বা লিস্টে পুশ করে দিয়েছি ।

word নামে একটি ফাকা স্ট্রিং নিয়েছি এবং contains অ্যারেতে একটি লুপ থ্রু করেছি । লুপটি ততক্ষণ চলবে যতক্ষণ পর্যন্ত contains এর সাইজ 0 থেকে বড় থাকবে । এবং প্রত্যেক ইটারেশনে word এর সাথে contains এর শেষ উপাদানটি রিমুভ হয়ে যোগ হতে থাকবে । এক পর্যায়ে আমাদের লুপটি শেষ হবে । তখন যদি word এবং str সমান হয় তাহলে funciton টি আমাদেরকে true রিটার্ন করবে নতুবা false রিটার্ন করবে ।

কোডের টাইম ও স্পেস উভয় কমপ্লেক্সিটি হবে ওর্ডার অব এন অর্থাৎ O(n) ।