โปรแกรมตรวจสอบว่าสตริงเป็นพาลินโดรมหรือไม่ด้วยคู่เทียบเท่าใน Python

สมมติว่าเรามีสตริงพิมพ์เล็กชื่อ s และรายการคู่ชื่อ pairs แต่ละสมาชิกใน pairs มีสองสตริง [a, b] โดยตัวอักษร a และ b ถือว่าเหมือนกัน หากมีคู่ [a, b] และ [b, c] แล้ว a และ b เทียบเท่า b และ c เทียบเท่า ดังนั้น a และ c ก็เทียบเท่า และค่าใดๆ ก็เทียบเท่ากับตัวมันเอง เราต้องตรวจสอบว่า s เป็นพาลินโดรมหรือไม่ภายใต้ความสัมพันธ์เทียบเท่านี้

เช่น ถ้าอินพุตคือ s = "raceckt", pairs = [["r", "t"], ["a", "k"], ["z", "x"]] ผลลัพธ์จะเป็น True เพราะ "a" = "k" และ "r" = "t" สตริงจึงกลายเป็น "racecar" ซึ่งเป็นพาลินโดรม

ขั้นตอนการแก้ปัญหา

1. g := adjacency list ของกราฟที่อาจมีสมาชิกซ้ำ
2. G := adjacency list ของกราฟที่ไม่มีสมาชิกซ้ำ:
   • สำหรับแต่ละ x, y ใน pairs เพิ่ม x เข้า g[x], y เข้า g[y], y เข้า g[x], x เข้า g[y]
3. กำหนดฟังก์ชัน dfs(a, so_far):
   • เพิ่ม a เข้า so_far
   • สำหรับแต่ละ elem ใน g[a] ถ้า elem ไม่อยู่ใน so_far เรียก dfs(elem, so_far)
4. จากเมธอดหลัก:
   • สำหรับแต่ละ key ใน g เรียก dfs(key, G[key])
   • สำหรับ i ในช่วง 0 ถึง floor(ขนาดของ s / 2):
     • ถ้า s[i] == s[-1-i] หรือ (s[i] ใน G[s[-1-i]] หรือ s[-1-i] ใน G[s[i]]) ข้ามรอบนี้
     • มิฉะนั้น คืนค่า False
5. คืนค่า 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