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

สมมติว่าเรามีสตริงตัวอักษรพิมพ์เล็กที่เรียกว่า s และยังมีรายการของคู่ที่เรียกว่า 'pairs' แต่ละองค์ประกอบที่เป็นคู่มีสองสตริง [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"]] เอาต์พุตจะ beTrue เพราะ "a" ="k" และ "r" ="t" ดังนั้น string สามารถเป็น "racecar" ซึ่งก็คือ palindrome

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

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