पायथन में समकक्ष जोड़े के साथ स्ट्रिंग की जांच करने का कार्यक्रम पैलिंड्रोम है या नहीं

मान लीजिए कि हमारे पास एक लोअरकेस वर्णमाला स्ट्रिंग है जिसे s कहा जाता है और इसमें जोड़े की एक सूची भी है जिसे 'जोड़े' कहा जाता है। जोड़े में प्रत्येक तत्व में दो तार होते हैं [ए, बी] जहां वर्ण 'ए' और 'बी' को समान माना जाता है। यदि [ए, बी] और [बी, सी] जैसे दो जोड़े हैं, तो हम कह सकते हैं कि ए और बी समकक्ष हैं और बी और सी समकक्ष हैं, इसलिए ए और सी भी समकक्ष हैं। और कोई भी मान a या b स्वयं के बराबर होता है। हमें यह जांचना है कि दिए गए तुल्यता संबंधों के साथ s एक पैलिंड्रोम है या नहीं।

इसलिए, यदि इनपुट s ="raceckt" जोड़े =[["r", "t"], ["a", "k"], ["z", "x"]] जैसा है, तो आउटपुट होगा सच है, क्योंकि "ए" ="के", और "आर" ="टी" इसलिए स्ट्रिंग "रेसकार" हो सकती है जो पैलिंड्रोम है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• g :=एक ग्राफ की आसन्न सूची जहां सूची में डुप्लिकेट तत्व हो सकते हैं
• G :=एक ग्राफ़ की आसन्न सूची जिसमें डुप्लिकेट तत्व नहीं होंगे
  • प्रत्येक x के लिए, y जोड़े में, करें
  • g[x] के अंत में x डालें
  • g[y] के अंत में y डालें
  • g[x] के अंत में y डालें
  • g[y] के अंत में x डालें
• एक फ़ंक्शन को परिभाषित करें dfs() । इसमें एक, बहुत दूर
. लगेगा
• so_far में a डालें
• g[a] में प्रत्येक तत्व के लिए, करें
  • यदि तत्व so_far में नहीं है, तो
    • dfs(elem, so_far)
• मुख्य विधि से, निम्न कार्य करें -
• जी में प्रत्येक कुंजी के लिए, करें
  • dfs(कुंजी, G[कुंजी])
  • मैं के लिए 0 की सीमा में (s / 2 का आकार), do
    • यदि s[i] s के समान है [s -1-i का आकार] या (s[i] G[s[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