প্যালিনড্রোম

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

source – https://www.deviantart.com/rose-xx-15412/art/Palindrome-Cow-364640478

একটি স্ট্রিং প্যালিন্ড্রোম কী না, সেটি পরীক্ষা করার উপায় কী? একটি উপায় হচ্ছে, স্ট্রিংটি উলটে দিয়ে আরেকটি স্ট্রিং তৈরি করা। তারপর তাদের মধ্যে তুলনা করে দেখা।

কাজটি আমরা পাইথন ব্যবহার করে খুব সহজেই করে ফেলতে পারি।

def is_palindrome(s):
    return s == s[::-1]

আবার আমরা স্ট্রিংয়ের মাঝামাঝি থেকে শুরু করে একটি একটি করে অক্ষর তুলনা করেও প্যালিনড্রেম পরীক্ষা করতে পারি।

def is_palindrome(s):
    l = len(s)
    indx1 = l // 2 - 1
    indx2 = (l + 1) // 2
    while indx1 >= 0 and indx2 < l:
        if s[indx1] != s[indx2]:
            return False
        indx1, indx2 = indx1 - 1, indx2 + 1

    return True

দুটি ফাংশনই একই উদ্দেশ্য সাধন করবে, কিন্তু একটু আলাদভাবে। এখন পাঠকদের কাছে প্রশ্ন – প্রথম ও দ্বিতীয় ফাংশনের টাইম ও স্পেস কমপ্লেক্সিটি কত?