# 1. Tóm tắt đề bài

Cho một mảng các xâu, hãy nhóm các **anagram** lại với nhau. Kết quả có thể được trả về trong bất cứ thứ tự nào.

**Anagram** là một từ hoặc cụm từ được tạo thành bằng cách sắp xếp lại các chữ cái của một từ hoặc cụm từ khác, thường sử dụng tất cả các chữ cái gốc đúng một lần.


### Giới hạn

$n = strs.length$
$k = strs[i].length$
- $1 \le n \le 10^4$
- $0 \le k \le 100$
- $strs[i]$ chỉ chứa các ký tự tiếng Anh in thường

# 2. Tóm tắt lời giải

**Độ phức tạp dự tính: $O(n \cdot sort(k))$**
($sort(k)$ là độ phức tạp thời gian của thuật toán dùng để sort xâu độ dài $k$)

Để ý rằng với 2 từ là anagram của nhau, nếu sort các ký tự trong từ theo thứ tự bảng chữ cái thì 2 từ đó cùng trở thành 1 từ.

Đọc câu trên thì chắc các bạn nghĩ ngay ra hướng làm rồi: dùng **HashMap** để map một anagram "gốc" với danh sách các anagram của nó.

# 3. Lời giải chi tiết

Làm như trên thôi, cũng không có gì phức tạp cả.

**Code mẫu tại [đây](https://leetcode.com/problems/group-anagrams/submissions/1167441481?envType=daily-question&envId=2024-02-06).**

> **_Note_**:
>
> Vì các xâu trong mảng ban đầu chỉ chứa các ký tự tiếng Anh in thường, bạn hoàn toàn có thể dùng Counting Sort để đưa độ phức tạp thời gian của sort về $O(k)$ và bộ nhớ mở rộng $O(26) = O(1)$.
>
> Tuy nhiên mình chọn code mẫu là cách dùng `sort()` của thư viện ngôn ngữ. Một phần lí do là vì với $k$ đủ nhỏ như giới hạn bài toán, sự khác biệt về thời gian chạy giữa 2 thuật toán không đáng kể, vậy nên việc tối ưu một thao tác này có thể coi là không cần thiết khi làm việc ngoài thế giới thực.
>
> Phần còn lại là liên quan đến thư viện của ngôn ngữ: `sort()` trong Python dùng [Timsort](https://en.wikipedia.org/wiki/Timsort) là thuật toán sort "thông minh" phù hợp với nhiều loại real-world data, không những thế nó còn được cài đặt tối ưu bằng C nhanh hơn tất cả các phương pháp sort thủ công trong Python.
> Vậy nên với những ngôn ngữ "chậm" như Python thì cái gì có trong thư viện thì cứ dùng thôi, không cần Reinvent the wheel làm gì cả :P
>
> Nếu muốn bạn vẫn có thể tham khảo code khi dùng Counting Sort tại [đây](https://leetcode.com/problems/group-anagrams/submissions/1167441971/?envType=daily-question&envId=2024-02-06).

### Độ phức tạp thuật toán

Thời gian: $O(n \cdot k \cdot log(k))$

Bộ nhớ mở rộng: $O(n \cdot k)$

# 4. Kết luận & Gợi ý mở rộng

Một bài vận dụng Hash Table khá dễ, tuy nhiên trước khi đến được hướng làm tối ưu phải có những quan sát nhất định.

Các bạn có thể làm thêm những bài có hướng giải tương tự dưới đây:
- [Valid Anagram](https://leetcode.com/problems/valid-anagram/description/)
- [Find Resultant Array After Removing Anagrams](https://leetcode.com/problems/find-resultant-array-after-removing-anagrams/description/)