[Day 13] Leetcode 49. Group Anagrams (C++)

前言

中秋连假第一天，来开启一系列的题目练习~ 今天挑战的是top 100 liked中hash table相关的题目─49. Group Anagrams。
所谓Anagrams就是可以用同样的一组字元重新排列组合的字串们~ 可以思考一下你会怎麽做呢？

想法

先不论是否为hash table类型的题目，遇到了要归类的情形，会想到的就是要让它们可以对到同一个类，而在这种情况下，用map或unordered_map就再适合不过了~ 而map跟unordered_map顾名思义就差在是否会对map里的key进行排序，可以视情况采用。
那要怎麽怎麽让同一组anagrams归到同一类呢？我们可以知道如果是属於同一组anagrams，字串里面的字元出现频率必定一样，例如abcc跟ccba，都是ax1，bx1，cx2的情形，那直觉的方式就是再做一次字串统计表，让每个频率组合变成一个key，例如"a1b1c2"，每次统计字串所花费的时间就是O(n)。
不过，後来我采用的是另外一种做法，虽然时间复杂度略高一些，但写起来会比较简单一点，不用另外自己写一个函式，就是用sort。因为既然组成的元素跟频率都一样，那这个字串sort过之後的string应该也会相等，例如abcc、ccba，排序都会变成abcc。
而字串的sort就跟vector的sort差不多：sort(s.begin(),s.end())，不过sort的时间复杂度就是O(nlogn)了。
藉着算出每个string的key，我们就可以用map来把sort後的string当key，而不断push_back属於该类的string；最後则再遍历整个map来存到答案中。程序码如下：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        // key as sorted string
        map<string, vector<string>> ansM;
        vector<vector<string>> ans;
        // group by sorted string
        string sortedS;
        for(int i=0;i<strs.size();++i){
            sortedS = strs[i];
            sort(sortedS.begin(),sortedS.end());
            ansM[sortedS].push_back(strs[i]);
        }
        // push saved map to ans
        for(auto &i:ansM){
            ans.push_back(i.second);
        }
        return ans;
        
    }
};

时间复杂度应是O(nklogk)，n为总共string的数量，而k则为每个string的长度。
至於前面用"a1b1c2"这种字串当key的方式，也可以自行实作看看，理论上可以达到更佳的时间复杂度(O(nlogk))。

结语

假日就有比较充裕的时间练习新题目了，趁有空的时候多累积一些吧XD