Gom nhóm Anagram từ danh sách cho trước trong Python

Trong hướng dẫn này, ta viết chương trình gom tất cả anagram trong một list. Trước hết, xem anagram là gì.

Hai chuỗi bất kỳ có cùng ký tự nhưng thứ tự khác nhau gọi là anagram.

Trước khi đi vào giải pháp, xem ví dụ.

Đầu vào

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

Đầu ra

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

Ta chia vấn đề thành hai phần. Trước, viết hàm kiểm tra hai chuỗi có phải anagram không. Các bước viết mã kiểm tra anagram:

• Khởi tạo chuỗi.
• Sắp xếp cả hai chuỗi.
• Nếu chuỗi đã sắp xếp bằng nhau trả về True ngược lại False.

Ví dụ

# Hàm lambda đơn giản kiểm tra hai chuỗi có phải anagram không
are_anagrams = lambda x, y: str(sorted(x.lower())) == str(sorted(y.lower()))
# Gọi hàm
print(are_anagrams('cat', 'tac'))
print(are_anagrams('cat', 'Tac'))
print(are_anagrams('cat', 'dog'))

Kết quả

Nếu chạy mã trên, bạn sẽ nhận được kết quả sau.

True
True
False

Bây giờ ta biết kiểm tra hai chuỗi anagram. Nhưng chưa đủ giải quyết bài toán. Ta cần gom (lưu) tất cả anagram từ list thành các sublist.

Làm sao giải quyết?

Thực hành tốt là dùng dictionary gom nhóm phần tử. Ta có một key cho các anagram liên quan. Hơi rối nếu mới học Python. Xem các bước đạt mục tiêu.

• Khởi tạo list chuỗi.
• Khởi tạo dictionary rỗng.
• Lặp qua list.
  • Sắp xếp chuỗi.
  • Kiểm tra có trong dictionary không.
  • Nếu có, thêm chuỗi vào list của nó.
  • Ngược lại, khởi tạo key với list chứa chuỗi hiện tại lưu anagram.
• In tất cả giá trị dictionary dạng list.

Ví dụ

# Khởi tạo list chuỗi
anagrams = ['cat', 'dog', 'fired', 'god', 'pat', 'tap', 'fried', 'tac']
# Khởi tạo dict rỗng
grouped_anagrams = {}
# Lặp qua list gom tất cả anagram
for string in anagrams:
    # Sắp xếp chuỗi
    sorted_string = str(sorted(string))
    # Kiểm tra chuỗi trong dict
    if sorted_string in grouped_anagrams:
        # Thêm chuỗi vào nhóm anagram
        grouped_anagrams[sorted_string].append(string)
    else:
        # Khởi tạo list với chuỗi hiện tại
        grouped_anagrams[sorted_string] = [string]
# In giá trị dict (nhóm anagram)
print(list(grouped_anagrams.values()))

Kết quả

Nếu chạy mã trên, bạn sẽ nhận được kết quả sau.

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

Kết luận

Bạn có thể giải quyết bằng cách tiếp cận khác. Có cấu trúc dữ liệu defaultdict giúp tránh kiểm tra key trong dictionary. Bạn khám phá và thay đổi mã cho phù hợp.

Nếu có thắc mắc, hãy đề cập ở phần bình luận.