โปรแกรมหาขนาดกลุ่มอนากรามมากที่สุดจากรายการคำใน Python

สมมติว่าเรามีรายการสตริง words เราต้องจัดกลุ่มคำที่เป็นอนากราม (anagrams) ร่วมกัน และคืนค่าขนาดของกลุ่มที่ใหญ่ที่สุด

ตัวอย่างเช่น หาก words = ["xy", "yx", "xyz", "zyx", "yzx", "wwwww"] ผลลัพธ์คือ 3 จากกลุ่ม ["xyz", "zyx", "yzx"]

ขั้นตอนการแก้ปัญหา (Hash Map + Sorting Characters)

1. lookup = {} (แมปจาก sorted string -> count)
2. res = 0
3. สำหรับแต่ละ word ใน words:
   • p = "".join(sorted(word)) (signature ของ anagram)
   • lookup[p] = lookup.get(p, 0) + 1
   • res = max(res, lookup[p])
4. คืนค่า res

ตัวอย่างโค้ด Python

class Solution:
    def solve(self, words):
        lookup = {}
        res = 0
        
        for word in words:
            p = "".join(sorted(word))
            lookup[p] = lookup.get(p, 0) + 1
            res = max(res, lookup[p])
        
        return res

ob = Solution()
words = ["xy", "yx", "xyz", "zyx", "yzx", "wwwww"]
print(ob.solve(words))  # Output: 3

อินพุต

["xy", "yx", "xyz", "zyx", "yzx", "wwwww"]

เอาต์พุต

3