Bài 49 Leetcode: Group Anagrams

Đề bài:

Cho một mảng các chuỗi `strs`, nhóm các từ đồng anagram lại với nhau. Bạn có thể trả về kết quả theo bất kỳ thứ tự nào.

Một 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 thường sử dụng tất cả các chữ cái gốc một lần duy nhất.

Ví dụ 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Ví dụ 2:

Input: strs = [""]
Output: [[""]]

Ví dụ 3:

Input: strs = ["a"]
Output: [["a"]]

Ràng buộc:

• 1 <= độ dài của strs <= 10^4
• 0 <= độ dài của strs[i] <= 100
• strs[i] chỉ gồm các chữ cái tiếng Anh thường.

Giải thích thuật toán bằng C ++

class Solution {
 public:
  vector<vector<string>> groupAnagrams(vector<string>& strs) {
    vector<vector<string>> ans;
    unordered_map<string, vector<string>> keyToAnagrams;

    for (const string& str : strs) {
      string key = str;
      ranges::sort(key);
      keyToAnagrams[key].push_back(str);
    }

    for (const auto& [_, anagrams] : keyToAnagrams)
      ans.push_back(anagrams);

    return ans;
  }
};

Đây là một giải thuật để nhóm các từ đồng anagram lại với nhau trong một mảng `strs`. Dưới đây là giải thích chi tiết về giải thuật:

1. Khởi tạo một vector 2 chiều `ans` để lưu trữ kết quả cuối cùng, tức là các nhóm các từ đồng anagram.

2. Khởi tạo một `unordered_map` có tên `keyToAnagrams` để ánh xạ mỗi khóa (key) là một chuỗi đã được sắp xếp theo thứ tự các chữ cái của một từ trong `strs`, và giá trị tương ứng với mỗi khóa là một vector các từ có cùng khóa đó.

3. Sử dụng một vòng lặp để duyệt qua từng từ `str` trong `strs`:

– Sao chép từ `str` vào một biến `key`.

– Sắp xếp `key` theo thứ tự các chữ cái bằng cách sử dụng hàm `sort` từ thư viện `ranges`. Điều này giúp tạo ra một khóa đại diện cho anagram của từ `str`.

– Thêm từ `str` vào vector tương ứng với khóa `key` trong `keyToAnagrams`.

4. Sử dụng một vòng lặp để duyệt qua mỗi cặp key và vector anagrams trong `keyToAnagrams`:

– Thêm vector `anagrams` vào vector `ans`, tạo thành một nhóm anagram.

5. Trả về vector 2 chiều `ans`, chứa các nhóm các từ đồng anagram.

Kết quả là một vector 2 chiều `ans` chứa các nhóm các từ đồng anagram trong mảng `strs`. Các nhóm được tạo ra theo bất kỳ thứ tự nào.

Giải thích thuật toán bằng Java

class Solution {
  public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> keyToAnagrams = new HashMap<>();

    for (final String str : strs) {
      char[] chars = str.toCharArray();
      Arrays.sort(chars);
      String key = String.valueOf(chars);
      keyToAnagrams.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
    }

    return new ArrayList<>(keyToAnagrams.values());
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
    dict = collections.defaultdict(list)

    for str in strs:
      key = ''.join(sorted(str))
      dict[key].append(str)

    return dict.values()