পাইথনে ইকুিভ্যালেন্স পেয়ার দিয়ে প্যালিনড্রোম চেক করা

একটি স্ট্রিং s এবং ইকুিভ্যালেন্স পেয়ার লিস্ট দেওয়া আছে। [a,b] মানে a এবং b সমান। ট্রানজিটিভিটি ধারণ করে (a=b, b=c ⇒ a=c)। এই রুল দিয়ে স্ট্রিং প্যালিনড্রোম কিনা চেক করুন।

ইনপুট উদাহরণ

s = "raceckt"
pairs = [["r","t"], ["a","k"], ["z","x"]]

আউটপুট: True (a=k, r=t ⇒ "racecar" প্যালিনড্রোম)

অ্যালগরিদম

1. অ্যাডজেসেন্সি লিস্ট বানান (গ্রাফ)՝ পেয়ার থেকে।
2. DFS দিয়ে প্রতিটি নোডের সব একুিভ্যালেন্ট নোড খুঁজে G-এ স্টোর করুন।
3. স্ট্রিংয়ের দুি cabeza থেকে মিলিয়ে চেক করুন: সমান নয় কিন্তু একুিভ্যালেন্ট হলে OK।

পাইথন কোড

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(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

# টেস্ট
print(solve("raceckt", [["r","t"],["a","k"],["z","x"]]))  # True

ব্যাখ্যা

ইকুিভ্যালেন্স রিলেশন = কানেক্টেড কম্পোনেন্ট। DFS দিয়ে প্রতিটি কম্পোনেন্টের সব মেম্বার খুঁজে প্যালিনড্রোম চেক করা হয়।