একটি স্ট্রিং-এর অক্ষরগুলি পাইথনে O(1) অতিরিক্ত স্থানে একটি প্যালিনড্রোম তৈরি করে কিনা তা পরীক্ষা করুন

ধরুন আমরা একটি স্ট্রিং s আছে. এই স্ট্রিংটিতে ছোট হাতের অক্ষর, অন্যান্য বিশেষ অক্ষর এবং সংখ্যা থাকতে পারে। আমাদের পরীক্ষা করতে হবে যে স্ট্রিংটিতে উপস্থিত অক্ষরগুলি প্যালিনড্রোমিক কিনা। এখানে একটি সীমাবদ্ধতা হল এই সমস্যাটি সমাধান করার জন্য আমাদের অতিরিক্ত স্থান ব্যবহার করার অনুমতি নেই।

সুতরাং, যদি ইনপুটটি s ="ra$5ce58car" এর মত হয়, তাহলে আউটপুট হবে True, যেহেতু অক্ষরগুলি "racecar" গঠন করছে যা প্যালিনড্রোম।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

একটি ফাংশন সংজ্ঞায়িত করুন first_letter_index()। এটি str, left, right
সূচক :=-1
বাম থেকে ডান + 1 রেঞ্জের জন্য,
- যদি str[i] ছোট হাতের বর্ণমালা হয়, তাহলে
  - সূচক :=i
  - লুপ থেকে বেরিয়ে আসুন
রিটার্ন সূচক
একটি ফাংশন সংজ্ঞায়িত করুন last_letter_index()। এটি str, left, right
সূচক :=-1
আমি বাম থেকে ডানে পরিসরে - 1, 1 দ্বারা হ্রাস করুন,
- যদি str[i] ছোট হাতের বর্ণমালা হয়, তাহলে
  - সূচক :=i
  - লুপ থেকে বেরিয়ে আসুন
- রিটার্ন সূচক
- প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন:
- বামে :=0, ডানে :=str - 1 এর আকার
- পতাকা :=সত্য
- আমি 0 থেকে str এর মাপের রেঞ্জের জন্য,
  - বাম :=first_letter_index(str, left, right)
  - ডান:=last_letter_index(str, right, left)
  - যদি ডান <0 বা বাম <0, তারপর
    - লুপ থেকে বেরিয়ে আসুন
  - যদি str[left] str[right] এর মত হয়, তাহলে
    - বাম :=বাম + 1
    - ডান :=ডান - 1
    - পরবর্তী পুনরাবৃত্তির জন্য যান
  - পতাকা :=মিথ্যা
    - লুপ থেকে বেরিয়ে আসুন
রিটার্ন পতাকা

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ কোড

def first_letter_index(str, left, right):
   index = -1
   for i in range(left, right + 1):
      if str[i] >= 'a' and str[i] <= 'z' :
         index = i
         break
 
   return index

def last_letter_index(str, left, right):
   index = -1
   for i in range(left, right - 1, -1) :
      if str[i] >= 'a' and str[i] <= 'z':
         index = i
         break
 
   return index

def solve(str):
   left = 0
   right = len(str) - 1
   flag = True
 
   for i in range(len(str)) :
      left = first_letter_index(str, left, right)
      right = last_letter_index(str, right, left)
 
      if right < 0 or left < 0:
         break
      if str[left] == str[right]:
         left += 1
         right -= 1
         continue
 
      flag = False
      break
 
   return flag
 
s = "ra$5ce58car"
print(solve(s))

ইনপুট

"ra$5ce58car"

আউটপুট

True