LeetCodeDay37 —— 字母异位词分组★★★

49. 字母异位词分组

描述

• 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例

输入:
  ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
  [
    ["ate","eat","tea"],
    ["nat","tan"],
    ["bat"]
  ]
说明：
  所有输入均为小写字母。
  不考虑答案输出的顺序。

思路

1. 暴力解法，将字符串数组中的字符串两两比较，相同的放在同一个Vector中
2. 利用容器Map<string, vector<string>>, 将字符串String排序后作 Key, 同 Key 的字符串放在一个桶内。

// 超时算法
class Solution_49_OverTime {
 public:
  vector<vector<string>> groupAnagrams(vector<string>& strs) {
    vector<vector<string>> ret;
    vector<bool> isTag;
    isTag.assign(strs.size(), false);
    for (int i = 0; i < strs.size(); ++i) {
      if (isTag[i]) continue;
      vector<string> tmp;
      tmp.push_back(strs[i]);
      for (int j = i + 1; j < strs.size(); ++j) {
        if (isAnagram(strs[i], strs[j])) {
          tmp.push_back(strs[j]);
          isTag[j] = true;
        }
      }
      ret.push_back(tmp);
    }
    return ret;
  }
  bool isAnagram(string s1, string s2) {
    sort(s1.begin(), s1.end());
    sort(s2.begin(), s2.end());
    return s1 == s2;
  }
};

// 错误的思路，字符和加位数并不能唯一确定字符串，如ac和bb
class Solution_49_Error {
 public:
  vector<vector<string>> groupAnagrams(vector<string>& strs) {
    vector<vector<string>> ret;
    unordered_map<int, int> hash;
    vector<int> weight;
    // 计算出每个字符串的权值
    for (string str : strs) {
      int tmp = 0;
      for (char ch : str) {
        tmp += ch - 'a';
      }
      weight.push_back(tmp * 10 + str.size());
    }
    // 根据权重分配异位词
    for (int i = 0; i < strs.size(); ++i) {
      auto iter = hash.find(weight[i]);
      if (iter == hash.end()) {
        hash[weight[i] = ret.size();
        ret.push_back({strs[i]});
      } else {
        ret[iter->second].push_back(strs[i]);
      }
    }
    return ret;
  }
};

// string 作 key, 将对应的字符串放入数组中
class Solution_49 {
 public:
  vector<vector<string>> groupAnagrams(vector<string>& strs) {
    vector<vector<string>> ret;
    unordered_map<string, vector<string>> mp;
    for(const string& str : strs){
      string t = str;
      sort(t.begin(), t.end());
      mp[t].push_back(str);
    }
    for(const auto& val : mp){
      ret.push_back(val.second);
    }
    return ret;
  }
};