กลุ่มของสตริงเทียบเท่าพิเศษใน Python

สมมติว่าเรามีอาร์เรย์ของสตริงที่เรียกว่า A การย้ายไปยัง S หนึ่งครั้งประกอบด้วยการสลับอักขระสองตัวที่จัดทำดัชนีของ S หรืออักขระที่ทำดัชนีคี่สองตัวของ S

ตอนนี้ สองสาย S และ T นั้นเทียบเท่าพิเศษถ้าหลังจากจำนวนการเคลื่อนไหวใด ๆ ไปยัง S แล้ว S ก็เหมือนกับ T ดังนั้นถ้า S ="zzxy" และ T ="xyzz" นั้นเทียบเท่ากันเป็นพิเศษเพราะเราอาจทำการเคลื่อนไหว เช่น "zzxy" เป็น "xzzy" เป็น "xyzz" ที่สลับ S[0] และ S[2] จากนั้น S[1] และ S[3]

ตอนนี้กลุ่มของสตริงที่เทียบเท่าพิเศษจาก A เป็นเซตย่อยที่ไม่ว่างของ A ในลักษณะที่ว่า -

ในทุกคู่ของสตริงในกลุ่มมีความพิเศษเทียบเท่าและกลุ่มที่มีขนาดที่ใหญ่ที่สุด (ไม่มีสตริง S ไม่อยู่ในกลุ่มเพื่อให้ S เป็นพิเศษเทียบเท่ากับทุกสตริงในกลุ่มนั้น) เราต้องหาจำนวน กลุ่มของสตริงเทียบเท่าพิเศษจาก A.

ดังนั้น หากอินพุตเป็น ["abcd","cdab","cbad","xyzz","zzxy","zzyx"] เอาต์พุตจะเป็น 3 เนื่องจากหนึ่งกลุ่มคือ ["abcd", " cdab", "cbad"] เนื่องจากทั้งหมดมีค่าเทียบเท่าพิเศษแบบคู่ และไม่มีสตริงอื่นใดที่พิเศษเทียบเท่ากับคู่เหล่านี้ ยังมีอีกสองกลุ่ม ได้แก่ ["xyzz", "zzxy"] และ ["zzyx"]

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

• โค้ด :=ชุดใหม่
• สำหรับแต่ละคำใน A ทำ
  • code :=เชื่อมสองสตริงด้วยดัชนีตำแหน่งคู่และอีกสตริงที่มีดัชนีตำแหน่งคี่
  • เพิ่มโค้ดลงในโค้ด
• ขนาดส่งคืนของรหัส

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

class Solution:
   def numSpecialEquivGroups(self, A):
      codes = set()
      for word in A:
         code = ''.join(sorted(word[::2])) +''.join(sorted(word[1::2]))
         codes.add(code)
      return len(codes)
ob = Solution()
print(ob.numSpecialEquivGroups(["abcd","cdab","cbad","xyzz","zzxy","z
zyx"]))

อินพุต

["abcd","cdab","cbad","xyzz","zzxy","zzyx"]

ผลลัพธ์

3