การจัดกลุ่ม Anagrams (คำอ่านคล้ายกัน) ใน Python

Anagrams คือ คำที่ประกอบด้วยตัวอักษรชุดเดียวกัน แต่เรียงลำดับต่างกัน (เช่น "cat" และ "tac", "listen" และ "silent")

Input/Output

Input:  ['cat', 'dog', 'fired', 'god', 'pat', 'tap', 'fried', 'tac']
Output: [['cat', 'tac'], ['dog', 'god'], ['fried', 'fired'], ['pat', 'tap']]

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

1. สร้างฟังก์ชันเช็ค Anagram: เรียงตัวอักษรทั้ง 2 คำ ถ้าเท่ากัน = Anagram
2. ใช้ Dictionary จัดกลุ่ม: Key = ตัวอักษรที่เรียงแล้ว, Value = ลิสต์คำ

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

ฟังก์ชันเช็ค Anagram

are_anagrams = lambda x, y: str(sorted(x.lower())) == str(sorted(y.lower()))

print(are_anagrams('cat', 'tac'))   # True
print(are_anagrams('cat', 'Tac'))   # True (case insensitive)
print(are_anagrams('cat', 'dog'))   # False

จัดกลุ่ม Anagrams ทั้งลิสต์

anagrams = ['cat', 'dog', 'fired', 'god', 'pat', 'tap', 'fried', 'tac']
grouped_anagrams = {}

for word in anagrams:
    sorted_word = str(sorted(word))
    if sorted_word in grouped_anagrams:
        grouped_anagrams[sorted_word].append(word)
    else:
        grouped_anagrams[sorted_word] = [word]

print(list(grouped_anagrams.values()))

ผลลัพธ์

[['dog', 'god'], ['pat', 'tap'], ['cat', 'tac'], ['fired', 'fried']]

การปรับปรุงด้วย defaultdict

from collections import defaultdict

anagrams = ['cat', 'dog', 'fired', 'god', 'pat', 'tap', 'fried', 'tac']
grouped = defaultdict(list)

for word in anagrams:
    grouped[str(sorted(word))].append(word)

print(list(grouped.values()))

Complexity: O(N * K log K) โดย N = จำนวนคำ, K = ความยาวคำเฉลี่ย (จากการ sort)