স্ট্রিং চেক করার প্রোগ্রাম প্যালিনড্রোম নাকি পাইথনের সমতুল্য জোড়ার সাথে নয়

ধরুন আমাদের কাছে s নামক একটি ছোট হাতের বর্ণমালার স্ট্রিং আছে এবং 'পেয়ার' নামক জোড়ার একটি তালিকাও রয়েছে। জোড়ায় প্রতিটি উপাদানের দুটি স্ট্রিং [a, b] আছে যেখানে 'a' এবং 'b' অক্ষরটিকে একই হিসাবে বিবেচনা করা হয়। যদি দুটি জোড়া থাকে যেমন [a, b] এবং [b, c], তাহলে আমরা বলতে পারি a এবং b সমতুল্য এছাড়াও b এবং c সমতুল্য, তাই a এবং cও সমতুল্য। এবং যে কোন মান a বা b নিজেই সমতুল্য। প্রদত্ত সমতুল্য সম্পর্কগুলির সাথে s একটি প্যালিনড্রোম কিনা তা আমাদের পরীক্ষা করতে হবে৷

সুতরাং, যদি ইনপুটটি s ="raceckt" জোড়া =[["r", "t"], ["a", "k"], ["z", "x"]] এর মত হয়, তাহলে আউটপুট হবে সত্য, কারণ "a" ="k", এবং "r" ="t" তাই স্ট্রিংটি "রেসকার" হতে পারে যা প্যালিনড্রোম।

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

g :=একটি গ্রাফের সংলগ্ন তালিকা যেখানে তালিকায় ডুপ্লিকেট উপাদান থাকতে পারে
G :=একটি গ্রাফের সংলগ্ন তালিকা যেখানে ডুপ্লিকেট উপাদান থাকবে না
- প্রতিটি x, y জোড়ায়, করুন
- g[x] এর শেষে x ঢোকান
- g[y] এর শেষে y ঢোকান
- g[x] এর শেষে y ঢোকান
- g[y] এর শেষে x ঢোকান
একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি একটি, so_far
এটি so_far এ ঢোকান
g[a]-এর প্রতিটি উপাদানের জন্য, করুন
- যদি elem so_far এর মধ্যে না থাকে, তাহলে
  - dfs(elem, so_far)
প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
g-এ প্রতিটি কী-এর জন্য করুন
- dfs(কী, G[key])
- 0 থেকে ফ্লোর (s / 2 এর মাপ) রেঞ্জের জন্য,
  - যদি s[i] হয় s[s-1-i এর আকার] অথবা (s[i] হয় G[s[s - 1-i]] বা s[-1 - i] G[s[i]]) , তারপর
    - পরবর্তী পুনরাবৃত্তির জন্য যান
  - অন্যথায়,
    - মিথ্যে ফেরত দিন
সত্য ফেরান

উদাহরণ

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

from collections import defaultdict
def solve(s, pairs):
   g = defaultdict(list)
   G = defaultdict(set)
   for x, y in pairs:
      g[x].append(x)
      g[y].append(y)
      g[x].append(y)
      g[y].append(x)

   def dfs(a, so_far):
      so_far.add(a)
      for elem in g[a]:
         if elem not in so_far:
            dfs(elem, so_far)

   for key in g:
      dfs(key, G[key])

   for i in range(0, len(s) // 2):
      if s[i] == s[-1 - i] or (s[i] in G[s[-1 - i]] or s[-1 - i] in G[s[i]]):
         continue
      else:
         return False
   return True

s = "raceckt"
pairs = [["r", "t"], ["a", "k"], ["z", "x"]]
print(solve(s, pairs))

ইনপুট

"raceckt", [["r", "t"], ["a", "k"], ["z", "x"]]

আউটপুট

True