Palindrome চেক করার Algorithm ও পাইথন প্রোগ্রাম

image source: pexels.com

Palindrome কী?

যদি কোনো শব্দ বা বাক্যের বর্ণগুলোকে ক্রমানুসারে পিছন দিক থেকেও সাজানো হয় তবুও শব্দ বা বাক্যটির কোনো পরিবর্তন না হয়, তবে তাকে Palindrome বলে। যেমনঃ madam বা racecar এদেরকে আপনি যেদিক থেকেই সাজান না কেন একই শব্দ পাবেন।

প্যালিনড্ৰোম (ইংরেজি: Palindrome) হল এমন কিছু বিশেষ শব্দ আর সংখ্যা যার আরম্ভ বা শেষ দুদিক থেকেই পড়লে শব্দের উচ্চারণ আর অৰ্থের কোন বদল হয় না; বা সংখ্যার মান একই থাকে (সংখ্যার ক্ষেত্ৰে)। মূল গ্ৰীক শব্দ প্যালিনড্ৰোমাস (অৰ্থ: Running back again) থেকে ইংরাজী প্যালিনড্ৰোম শব্দটি এসেছে ।বাংলা ভাষায় একে দ্বিমুখী শব্দ বা সংখ্যা বলা যায়। এধরণের দ্বিমুখী শব্দ বা বাক্য সাজাতে যারা দক্ষ তাঁদের ‘পেলিনড্ৰোমিস্ট’ বলা হয়।
প্যালিনড্ৰোম উদাহরণ: সরস, জলজ, কথক, নবজীবন, রমাকান্তকামার, MADAM, REFER, NOON, LEVEL, 11, 101, 10201
a word, phrase, or sequence that reads the same backwards as forwards, e.g. madam or racecar.
 — — — from Wikipedia
list of palindrome words, source: google search

এই প্রব্লেম সলভ করার জন্য আপনাকে রকেট সাইন্টিস্ট হতে হবেনা জাস্ট চিন্তা করতে হবে যে প্রোগ্রামে যে শব্দ টা ইনপুট নিবেন সেটাকে রিভার্স করলেও যদি একই থাকে, তবে তাই palindrome অন্যথায় ইহা palindrome শব্দ নয়।

Definition of Palindrome

এই কাজটা একাধিক ভাবে করা যাই। আমি এখানে বহুল ব্যবহৃত তিনটি পদ্ধতি নিয়ে আলোচনা করবো।

এলগোরিদম ১:

step-1: প্রথমে শব্দটাকে রিভার্স করতে হবে। 
step-2: রিভার্স শব্দটা অরিজিনাল শব্দের সাথে মিলিয়ে দেখতে হবে। যদি ঠিক থাকে তাহলে ইহা palindrome ।

তাহলে এবার কোড লেখা যাক। আমি এখানে পাইথন-৩ ব্যবহার করেছি।

#string reverse function
def reverse(s):
rev = ''

for ch in s:
rev = ch + rev
return rev

print(reverse('hello')) #olleh
print(reverse('madam')) #madam
#Palindrome checker
def is_palindrome_v1(s):
return s == reverse(s)

print(is_palindrome_v1('madam')) #True
print(is_palindrome_v1('python')) #False

এখানে প্রথমে একটি reverse(s) ফাংশন তৈরী করা হয়েছে স্ট্রিং রিভার্স করার জন্য। এই ফাংশন টা একটা স্ট্রিং ইনপুট নিবে সেই স্ট্রিং টা রিভার্স করে রাখার জন্য একটা empty স্ট্রিং ভ্যারিয়েবল rev ডিক্লেয়ার করা হয়েছে। অতঃপর লুপ চালিয়ে স্ট্রিং এর ক্যারেক্টর গুলোকে rev ভ্যারিয়েবল এ স্টোর করা হয়েছে। ফাইনালি rev ভ্যারিয়েবল টা রিটার্ন করা হয়েছে।

অতঃপর Palindrome চেকার ফাংশন তৈরী করা হয়েছে। এখানে যে স্ট্রিং ইনপুট দেয়া হবে তা রিভার্স ফাংশন এ পাস করা রিভার্স ওয়ার্ডটির সাথে মিলিয়ে দেখা হয়েছে। True হলে Palindrome অন্যথায় ইহা Palindrome নয়।

এলগোরিদম :

step-1: প্রথমে স্ট্রিং টিকে সমান দুই ভাগে ভাগ করতে হবে।
step-2: দ্বিতীয় অংশকে রিভার্স করতে হবে।
step-3: অতঃপর প্রথম অংশকে দ্বিতীয় অংশের সাথে মিলিয়ে দেখতে হবে।
step-4: এক্ষেত্রে স্ট্রিং এর length বিজোড় সংখ্যা হতে পারে তাই ফ্লোর হাফ (len(s) // 2) করতে হবে।
(অর্থাৎ যদি 'racecar' ওয়ার্ড টার কথা চিন্তা করা যাই। তবে দেখা যাবে এর length = 7। একে ফ্লোর হাফ করলে (7 // 2 = 3) পাওয়া যাবে। অতঃপর প্রথম অংশ শেষ অংশের সাথে মিলিয়ে দেখা হবে। মাঝের বর্ণ টা ignore করা হবে।)

তাহলে এবার কোড লেখা যাক।

#Palindrome checker
def is_palindrome_v2(s):
n = len(s)
return s[:n // 2] == reverse(s[n - n // 2:])


#string reverse function
def reverse(s):
rev = ''
for ch in s:
rev = ch + rev
return rev

print(is_palindrome_v2('mom')) #True
print(is_palindrome_v2('racecar')) #True
print(is_palindrome_v2('father')) #False

এখানেও রিভার্স ফাংশন টা ব্যবহার করা হয়েছে। কিন্তু পুরো ওয়ার্ডটা রিভার্স করা হয় নি। শুধুমাত্র শেষের অংশটুকু রিভার্স করা হয়েছে।

এলগোরিদম ৩:

এই এলগোরিদম এ স্ট্রিং এর প্রথম ক্যারেক্টার কে লাস্ট ক্যারেক্টার এর সাথে। সেকেন্ড ক্যারেক্টার কে সেকেন্ড লাস্ট ক্যারেক্টার এর সাথে এভাবে চেক করে করে বের করা হবে এটি পালিনড্রম কিনা।

#Palindrome checker
def is_palindrome_v3(s):
    i = 0
j = len(s) - 1
    while i < j and s[i] == s[j]:
i = i + 1
j = j - 1
    return j <= i

print(is_palindrome_v3('mom')) #True
print(is_palindrome_v3('racecar')) #True
print(is_palindrome_v3('father')) #False

এখানে i নামে একটা ভ্যারিয়েবল ডিক্লেয়ার করা হয়েছে। যার ইনিশিয়াল ভ্যালু ধরা হয়েছে শুন্য (0)। j নামে আরো একটা ভ্যারিয়েবল ডিক্লেয়ার করা হয়েছে যার ইনিশিয়াল ভ্যালু ধরা হয়েছে স্ট্রিং লেংথ এর চেয়ে ১ কম। 
অতঃপর চেক করা হয়েছে i যদি j এর চেয়ে ছোট হয় এবং স্ট্রিং এর i তম ভ্যালু স্ট্রিং এর j তম ভ্যালু এর সমান হয় তবে while লুপ চালিয়ে ফাস্ট to লাস্ট ক্যারেক্টার by ক্যারেক্টার চেক করা হয়েছে।

অতঃপর যদি j এর মান i এর চেয়ে ছোট বা সমান হয় তবে ইহা palindrome এবং True রিটার্ন করবে।

Bonus:

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

#Palindrome checker
def is_palindrome_v4(s):

return s == s[::-1]

print(is_palindrome_v4('mom')) #True
print(is_palindrome_v4('racecar')) #True
print(is_palindrome_v4('father')) #False

এটা কিভাবে হলো তা জানতে হলে palindrome in python লিখে google এ সার্চ দিন। stackoverflow তে সুন্দর করে বুঝানো আছে।

Thanks for reading.

Happy Coding :)