49.Group Anagramsを解いた

公開: 2024/10/22

問題

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

文字列strsの配列が与えられたら、アナグラムをグループ化しなさい。任意の順序で答えを返すことができる。

アプローチ

アナグラムかどうかを判定するためにソートした文字列をmapのキーとして、バリューにstrsの要素を格納する
strs配列の各要素をmapに格納するためにn回（strsの要素数）ループ
解答用の二次元配列resultsを用意してmapのバリューに格納されていアナグラムをresultsに追加していく
最初のループでn回、resultsに格納するループで最悪でもn回のループになるので時間計算量はO(n)となる

提出コード

/*
 * @lc app=leetcode id=49 lang=cpp
 *
 * [49] Group Anagrams
 */

// @lc code=start
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> sm;
        vector<vector<string>> results;

        for (string str : strs) {
            string original_str = str;
            sort(str.begin(), str.end());

            sm[str].push_back(original_str);
        }

        for (auto i = sm.begin(); i != sm.end(); i++) {
            results.push_back(i->second);
        }
        return results;
    }
};
// @lc code=end

改善案

resultsに格納するためのループを範囲for文にした方がスッキリ書けそうと思った。
http://www.nct9.ne.jp/m_hiroi/linux/cpp31.html

for (auto i = sm.begin(); i != sm.end(); i++) {
  results.push_back(i->second);
}

↓↓

for (auto m : sm) {
  results.push_back(m->second);
}