49. 字母异位词分组

49. 字母异位词分组 - 力扣（LeetCode）

class Solution {
public:
  vector<vector<string>> groupAnagrams(vector<string>& strs) {
    vector<vector<string>> Result;
    unordered_map<unordered_set<char>, int> SetIdx;
    for (const auto &S : strs) {
      unordered_set<char> Set(S);
      if (auto It = SetIdx.find(Set); It != SetIdx.end()) {
        Result[It->second].emplace_back(S);
      } else {
        SetIdx[Set] = Result.size();
        Result.emplace_back({S});
      }
    }
    return Result;
  }
};

只能说这种方法理论上来讲时间复杂度是小于直接排序的；但事实情况是 \(k\) 一般不会特别大，这就导致 \(\mathrm O\left(n\left(k+\left|\Sigma\right|\right)\right)\) 事实上含有远大于 \(\mathrm O\left(nk\log k\right)\) 的常数，所以下面的排序解法才会在时间和空间上都优于上述解法。

class Solution {
public:
  vector<vector<string>> groupAnagrams(vector<string>& strs) {
    vector<vector<string>> Result;
    unordered_map<string, int> StrIdx;

    for (const auto &S : strs) {
      string Key(S);
      sort(Key.begin(), Key.end());

      if (auto It = StrIdx.find(Key); It != StrIdx.end()) {
        Result[It->second].emplace_back(S);
      } else {
        StrIdx[Key] = Result.size();
        Result.push_back({S});
      }
    }
    return Result;
  }
};

但是对于这两种写法，都要注意：用 unordered_set 作 unordered_map 的键是不可行的，因为 std::hash<> 并没有针对 unordered_set 进行特化。下述代码是无法编译的。

class Solution {
public:
  vector<vector<string>> groupAnagrams(vector<string>& strs) {
    vector<vector<string>> Result;
    // XXX std::hash() doesn't have specialization for sets!
    unordered_map<unordered_set<char>, int> SetIdx;
    for (const auto &S : strs) {
      unordered_set<char> Set(S);
      if (auto It = SetIdx.find(Set); It != SetIdx.end()) {
        Result[It->second].emplace_back(S);
      } else {
        SetIdx[Set] = Result.size();
        Result.emplace_back({S});
      }
    }
    return Result;
  }
};

二刷

class Solution {
public:
  vector<vector<string>> groupAnagrams(vector<string>& strs) {
    map<array<char, 26>, vector<int>> SetIdx;
    vector<vector<string>> Result;
    for (int i = 0; i < strs.size(); ++i) {
      array<char, 26> Key;
      std::fill(Key.begin(), Key.end(), 0);
      for (char c : strs[i])
        ++Key[c - 97];
      SetIdx[Key].emplace_back(i);
    }
    for (auto I = SetIdx.begin(); I != SetIdx.end(); ++I) {
      Result.emplace_back();
      for (int i = 0; i < I->second.size(); ++i) {
        Result.back().emplace_back(strs[I->second[i]]);
      }
    }
    return Result;
  }
};

草，std::array神力，怎么把空间干到这么低的。当然这个的鲁棒性就比std::string差一点，但是好在不用排序，以及不会牵涉到std::string非常烂的性能。