剑指 Offer II 033. 变位词组

  • 这里有一个关键点，那就是unordered_map的键只能为单类型，不能为vector pair等类型。因此这里使用map来写，map底层是红黑树，可以支持vector作为键。
  • 这里也可以使用排序方法来写，因为字符串的长度是固定的，因此这样写不会超时，这种方法性能要高一点。

    map写法

    1. class Solution {
    2. public:
    3.   vector<vector<string>> groupAnagrams(vector<string>& strs) {
    4.       vector<vector<string>> res;
    5.       map<vector<int>, int> flag;
    6.       for(int i = 0; i < strs.size(); i++){
    7.           vector<int> char1(26);
    8.           for(auto c : strs[i]){
    9.               char1[c - 'a']++;
    10.           }
    11.           if(flag.find(char1)!=flag.end()){
    12.               res[flag[char1]].push_back(strs[i]);
    13.           } else {
    14.               flag[char1] = flag.size();
    15.               res.push_back({strs[i]});
    16.           }
    17.       }
    18.       return res;
    19.   }
    20. };

    排序写法

    ```cpp class Solution { public: vector> groupAnagrams(vector& strs) {
      unordered_map<string, vector<string>> mp;
  for (string& str: strs) {
      string key = str;
      sort(key.begin(), key.end());
      mp[key].emplace_back(str);
  }
  vector<vector<string>> ans;
  for (auto it = mp.begin(); it != mp.end(); ++it) {
      ans.emplace_back(it->second);
  }
  return ans;
    } };
<a name="BbL3f"></a>
### [剑指 Offer II 034. 外星语言是否排序](https://leetcode-cn.com/problems/lwyVBB/)

- 简单哈希，注意string类型是以\0结尾的，以此来判断是不是后面的已经结束了。
```cpp
class Solution {
public:
    bool isAlienSorted(vector<string>& words, string order) {
        unordered_map<char, int> hash;
        for(int i = 0; i < 26; i++){
            hash[order[i]] = i;
        }
        for(int i = 0; i < words.size()-1; i++){
            for(int j = 0; j < words[i].size(); j++){
                if(words[i+1][j]=='\0' || hash[words[i][j]] > hash[words[i+1][j]]){
                    return false;
                } else if(hash[words[i][j]] < hash[words[i+1][j]]){
                    break;
                }
            }
        }
        return true;
    }
};