Vui lòng đọc hiểu đề trước khi đọc bài viết này tại đây:
https://leetcode.com/problems/group-anagrams/description/
Table of Contents
1. Cách tiếp cận vấn đề
Bài toán yêu cầu chúng ta cần gom nhóm lại các chuỗi có cùng "Anagram" với nhau. Để gom nhóm được ta sẽ cần sử dụng map với key là "1 cái gì đó chung" và value chính là 1 list các chuỗi có cùng "Anagram".
Vậy thì bây giờ chúng ta cần xác định được cái gì đó chung giữa những thằng có chung "Anagram" với nhau. Như đã phân tích ở 1 bài viết khác cũng có liên hệ trực tiếp tới bài viết này:
Thì một tính chất quan trọng cần phải xét đến là khi 2 chuỗi được coi là Anagram của nhau, thì khi sắp xếp chúng, ta sẽ luôn thu được 1 chuỗi duy nhất và không đổi.
Ví dụ: String s = "anagram", String t ="nagaram"
2 chuỗi sau khi sắp xếp sẽ có cùng giá trị: "aaagmnr"
2. Solution & Phân Tích
2.1. Sử dụng Map với Sorting
Ta sẽ sử dụng 1 Map, với key là 1 chuỗi unique sau khi sắp xếp, value là list những chuỗi có cùng key, hay chúng là "Anagram" với nhau.
Dựa vào tính chất quan trọng đã nêu ở phần 1, chúng ta sẽ sử dụng 1 vòng for duy nhất để duyệt qua từng chuỗi tạm gọi là s, với mỗi chuỗi s ta sẽ tìm key trong map bằng việc sắp xếp chuỗi đó lại, từ key đó ta sẽ get ra được list chuỗi có cùng Anagram và add thêm chuỗi s đang xét hiện tại vào.
Input: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
"abt": ["bat"],
"ant": ["tan", "nat"],
"aet": ["eat", "tea", "ate"]
3 key tương ứng là: "abt", "ant" và "aet"
Time Complexity: O(n * mlogm)
Space Complexity: O(n)
Với n là số lượng phần tử của mảng input, còn m là chiều dài trung bình của từng chuỗi.
2.2. Sử dụng Map với Array
"Anagram" còn có 1 tính chất khá quan trọng khác đã được đề cập ở 1 bài viết trước đó:
Một chuỗi được coi là anagram của chuỗi còn lại, khi chúng có cùng chính xác số lượng các chữ cái khác nhau, cũng như số lần xuất hiện của mỗi chữ cái. Ví dụ: String s = "hello" => Có 1 chữ h, 1 chữ e, 1 chữ o và 2 chữ l.
Vì vậy ta có thể xác định những chuỗi có thể gom nhóm lại bằng cách tính xem chúng có cùng các loại chữ cái, cũng như có cùng số lượng xuất hiện của từng chữ cái hay không.
Ngoài ra, trong Java có hỗ trợ việc tạo chuỗi String từ 1 mảng ký tự character, ví dụ:
char[] carr = new char[26];
String key = new String(carr);
Điều này có nghĩa là với mỗi một mảng character khác nhau, ta sẽ có thể tạo được một String tương ứng khác nhau và ta có thể dùng String đó để làm key cho map ở trên. Và những chuỗi mà có cùng "Anagram" với nhau chắc chắn sẽ có cùng 1 key, vì chúng có cùng số loại chữ cái cũng như số lượng xuất hiện của từng chữ cái.
Kết hợp 2 điều kiện trên, ta hoàn toàn có thể tạo ra 1 mảng character để đếm số lần xuất hiện của các ký tự trong chuỗi đang xét, sau đó tạo ra key cho nó bằng đoạn code đã nêu ở ví dụ: String key = new String(carr); Sau đó get ra value là list các chuỗi đang có cùng key đó và add thêm giá trị mới là chuỗi đang xét hiện tại vào.
Chi tiết hơn, ta sẽ sử 1 mảng gồm 26 ô bộ nhớ, tương ứng với 26 ký tự trong bảng chữ cái alphabet, sau đó xác định ký tự đang duyệt là ở ô nhớ nào (bằng cách lấy ký tự "a" làm chuẩn, trừ ký tự đang xét cho ký tự "a", đằng sau nó sẽ dùng mã ascii là 1 số nguyên để thực hiện phép trừ), rồi đếm và tăng số lượng xuất hiện của chữ cái đó, cuối cùng gán ngược lại vào đúng vị trí của nó trong mảng.
Nhưng khoan, bạn có thắc mắc kết quả đếm được là 1 số nguyên kiểu integer kia mà? Làm sao ta có thể gán nó vào trong mảng ký tự character được? Về cơ bản thì chúng chỉ khác về giá trị lưu trữ mà thôi, khi ta gán 1 số nguyên integer vào 1 phần tử trong mảng character, thì nó sẽ xem số nguyên đó như mã ascii và chuyển về ký tự character tương ứng, ví dụ ký tự "a" xuất hiện 32 lần thì khi ta gán carr["a" - "a"] = 32 <=> carr[0] = 32 thì phần tử ở index 0 lúc này không thật sự lưu số 32, mà nó lưu ký tự có mã ascii 32 chính là ký tự space, hay khoảng trắng.
Khi biến đếm quá nhỏ, dẫn đến ascii nhỏ và không có 1 ký tự cụ thể để dễ demo nên mình sẽ không làm gif demo cho solution này, thay vào đó là bảng ascii để các bạn tiện theo dõi, và lưu ý ràng buộc của bài toán này cho chiều dài max của chuỗi chỉ là 100, nên giá trị trong trường hợp xấu nhất cũng không vượt qua khỏi bảng ascii này (max 127)
Space Complexity: O(n)
Với n là số lượng phần tử của mảng input, còn m là chiều dài trung bình của từng chuỗi.
3. Code
Mình sẽ sử dụng solution với char array để code vì nó tối ưu hơn về mặt thời gian:
