Leetcode 49: anagram

Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.

本题要求找出符串array里面所有的相同构词法的词。
anagram: 互为anagram的词所组成的char是相同的。
如何判断两个string 是否互为anagram? -> 
M1: 利用map，将第一个词存入map，key: char, value: counter，对第二个词中的char进行匹配，如果能够完全匹配，返回true; 时间复杂度是O（n）空间复杂度是O（n)
M2: anagram由于是由 相同的char组成，所以对anagram的字符串进行排序，这两个字符串是完全相同的。时间复杂度是O（nlogn）空间复杂度是O（1）
在本题中，要求找出一串字符串中按构词法进行分组，如果利用M1来对字符串进行两两配对，那么时间复杂度是O（n^2), 空间复杂度是O（n）; 如果利用M2对所有单词先排序，那么互为anagram的词结果是相同的，利用一个map，key： 排序后的词，value： 排序前的词，那么相同的anagram就直接分出来了。时间复杂度是O（k*nlongn)， 空间复杂度O（n）

所以，一个问题有多种解决方法，不能说哪个方法好或者不好，在不同的题目环境之下，应该合理选择解决问题的方法。
class Solution {
public:
    vector<string> anagrams(vector<string>& strs) {
        vector<string> rst;
        //sanity check
        if (strs.size() == 0) return rst;
        map<string, vector<string>> smap;
        for (int i = 0; i < strs.size(); i++) {
            string tmp = strs[i];
            sort(tmp.begin(), tmp.end());
            smap[tmp].push_back(strs[i]);
        }
        map<string, vector<string>> :: iterator it= smap.begin();
        for (; it != smap.end(); it++) {
            if ((it->second.size()) > 1) {
                for (int i = 0; i < it->second.size(); i++) {
                    rst.push_back(it->second[i]);
                }
            }
        }
        return rst;
       
    }
};