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

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

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

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

• g := एक ग्राफ की एडजेंसी सूची जहां सूची में डुप्लिकेट तत्व हो सकते हैं
• G := एक ग्राफ की एडजेंसी सूची जहां डुप्लिकेट तत्व नहीं होंगे:
  • pairs में प्रत्येक x, y के लिए, करें:
    • x को g[x] के अंत में डालें
    • y को g[y] के अंत में डालें
    • y को g[x] के अंत में डालें
    • x को g[y] के अंत में डालें
• dfs() फ़ंक्शन परिभाषित करें। यह a, so_far लेगा:
  • a को so_far में डालें
  • g[a] में प्रत्येक elem के लिए, करें:
    • यदि elem so_far में नहीं है, तो:
      • dfs(elem, so_far)
• मुख्य विधि से, निम्नलिखित करें:
  • g में प्रत्येक कुंजी के लिए, करें:
    • dfs(key, G[key])
  • i के लिए 0 से floor(s का आकार / 2) तक की रेंज में, करें:
    • यदि s[i] s[s का आकार - 1 - i] के समान है या (s[i] G[s[s का आकार - 1 - i]] में है या s[-1 - i] G[s[i]] में है), तो:
      • अगले पुनरावृत्ति के लिए जाएं
    • अन्यथा:
      • False लौटाएं
• True लौटाएं

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

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