[演算法題目] Group Anagrams

本題資訊

難度：medium
使用語言：C++
相關概念：Strings

題目敘述

Write a function that takes in an array of strings and groups anagrams together.
Anagrams are strings made up of exactly the same letters, where order doesn’t matter. For example, "cinema" and "iceman" are anagrams; similarly, "foo" and "ofo" are anagrams.

Your function should return a list of anagram groups in no particular order.

Input:

words = ["yo", "act", "flop", "tac", "foo", "cat", "oy", "olfp"]

Output:

[["yo", "oy"], ["flop", "olfp"], ["act", "tac", "cat"], ["foo"]]

這一題是要我們把所有「易位構詞」分組。

Idea

剛開始拿到這題有一點慌亂，除了判斷是否為 anagram 之外又要分組，感覺上會巡覽好幾次。但是像這種同性質要分組的題目類型，常常使用 unordered_map，處理上會很方便。如果要用這種方法的話，如何將不同的單字成功判斷成在同一組就是關鍵。

Anagram 的判斷其實很簡單，長度相同、成分相同，只是順序不同，所以搞定順序似乎就有搞頭。剛好字串也是能夠排序的，這裡我們利用 sort 將單字排序後當作 key，而原單字則當作 value 堆疊在後面，類似這樣：

如果搞定這個 map，接下來輸出就簡單多了。

#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

vector<vector<string>> groupAnagrams(vector<string> words) {
  unordered_map<string, vector<string>> anag;
  vector<vector<string>> result = {};
  
  for (auto word : words){
    string sorted = word;
    sort(sorted.begin(), sorted.end());
    if (anag.find(sorted) != anag.end()){
      anag[sorted].push_back(word);
    } else {
      anag[sorted] = vector<string>{word};
    }
  }

  for (auto word : anag){
    result.push_back(word.second);
  }
  return result;
}

時間複雜度：\(O(wn\log(n))\)。\(w\) 是指 words 長度、\(n\) 是指 word 最大長度。
空間複雜度：\(O(wn)\)