Chương trình kiểm tra chuỗi có phải là palindrome hay không với các cặp tương đương trong Python

Giả sử chúng ta có một chuỗi chữ cái viết thường được gọi là s và cũng có một danh sách các cặp được gọi là 'cặp'. Mỗi phần tử trong cặp có hai chuỗi [a, b] trong đó ký tự 'a' và 'b' được coi là giống nhau. Nếu có hai cặp như [a, b] và [b, c] thì ta có thể nói a và b tương đương còn b và c tương đương nên a và c cũng tương đương. Và bất kỳ giá trị a hoặc b nào cũng tương đương với chính nó. Chúng ta phải kiểm tra xem s có phải là palindrome hay không với các quan hệ tương đương đã cho.

Vì vậy, nếu đầu vào giống như s ="raceckt" pair =[["r", "t"], ["a", "k"], ["z", "x"]], thì đầu ra sẽ beTrue, bởi vì "a" ="k" và "r" ="t" nên chuỗi có thể là "racecar" là palindrome.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• g:=danh sách gần kề của một biểu đồ trong đó danh sách có thể chứa các phần tử trùng lặp
• G:=danh sách gần kề của một biểu đồ trong đó sẽ không chứa các phần tử trùng lặp
  • đối với mỗi x, y theo cặp, thực hiện
  • chèn x vào cuối g [x]
  • chèn y vào cuối g [y]
  • chèn y vào cuối g [x]
  • chèn x vào cuối g [y]
• Định nghĩa một hàm dfs (). Điều này sẽ mất một, so_far
• chèn một vào so_far
• đối với mỗi độ tuổi tính bằng g [a], thực hiện
  • nếu elem không có trong so_far, thì
    • dfs (elem, so_far)
• Từ phương pháp chính, hãy thực hiện như sau -
• đối với mỗi phím trong g, hãy thực hiện
  • dfs (key, G [key])
  • đối với tôi trong phạm vi từ 0 đến tầng của (kích thước s / 2), hãy thực hiện
    • nếu s [i] giống với s [kích thước của s -1-i] hoặc (s [i] bằng G [s [kích thước của s-1-i]] hoặc s [-1 - i] trong G [s [i]]), sau đó
      • chuyển sang lần lặp tiếp theo
    • nếu không,
      • trả về Sai
• trả về True

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

"raceckt", [["r", "t"], ["a", "k"], ["z", "x"]]

Đầu ra

True