Nhóm và in anagram cùng nhau trong Python (List & Dictionary)

Cho danh sách từ, nhóm các từ là anagram của nhau (cùng chữ cái, khác thứ tự) và in ra. Sử dụng dictionary với key là chuỗi đã sắp xếp.

Thuật toán

1. Khởi tạo dict rỗng: key = sorted word, value = list các word gốc.
2. Duyệt từng từ: sort ký tự → key. Thêm từ vào dict[key].
3. Duyệt dict: in các nhóm có size > 1 (hoặc in tất cả).

Mã nguồn

words = ["apple", "orange", "grapes", "pear", "peach", "listen", "silent", "enlist"]

anagrams = {}

for word in words:
    key = "".join(sorted(word))
    if key in anagrams:
        anagrams[key].append(word)
    else:
        anagrams[key] = [word]

# In các nhóm anagram
for key, group in anagrams.items():
    if len(group) > 1:
        print(f"Group '{key}': {group}")

# Hoặc gộp thành 1 chuỗi
result = " ".join(" ".join(group) for group in anagrams.values())
print(result)

Kết quả

Group 'eilnst': ['listen', 'silent', 'enlist']
apple orange grapes pear peach listen silent enlist

Cách ngắn gọn với defaultdict

from collections import defaultdict

anagrams = defaultdict(list)
for word in words:
    anagrams["".join(sorted(word))].append(word)

for group in anagrams.values():
    if len(group) > 1:
        print(group)

Độ phức tạp

• Thời gian: O(N * K log K) với N số từ, K độ dài trung bình (do sort).
• Không gian: O(N * K).
• Tối ưu: dùng tuple count 26 chữ cái làm key → O(N * K).

Kết luận

Kỹ thuật "sort làm key" là chuẩn cho bài toán nhóm anagram. Áp dụng rộng rãi trong LeetCode (Group Anagrams), NLP, spell check.