0049. Group Anagrams ==================== 题目信息 -------- :题号: 0049. 字母异位词分组 :难度: Medium :主题: 字符串、哈希表、规范键、字符频次 :原题: `LeetCode 0049 `_ :重点: 从反复比较是否为异位词,推导到为每个字符串计算唯一组签名并一次归组 题目重述 -------- 给定一个字符串数组 ``strs``,其中每个字符串只包含小写英文字母。请把互为字母异位词的字符串放入同一组, 并返回所有分组。 两个字符串互为字母异位词,当且仅当它们包含完全相同的字母,并且每种字母的出现次数也完全相同。 字符串内部字母的排列顺序不影响所属分组。每个输入字符串都必须保留一次;若相同字符串在输入中出现多次, 结果中也必须保留相同次数。分组之间以及同一组内部的顺序均不限。 约束为 ``1 <= strs.length <= 10^4``、``0 <= strs[i].length <= 100``。 自建示例 -------- .. code-block:: text 输入:strs = ["arc", "car", "rat", "tar", "elbow", "below", "arc", ""] 输出:[["arc", "car", "arc"], ["rat", "tar"], ["elbow", "below"], [""]] ``"arc"`` 与 ``"car"`` 的三个字母及次数相同,因此属于同一组;输入中的第二个 ``"arc"`` 仍须保留。 空字符串的 26 种字母次数全为零,也有唯一签名。 C++ 实现 -------- .. code-block:: cpp #include #include #include #include #include #include class Solution { private: bool haveSameFrequency(const std::string& first, const std::string& second) { if (first.size() != second.size()) return false; std::array count{}; for (char ch : first) ++count[ch - 'a']; for (char ch : second) { if (--count[ch - 'a'] < 0) return false; } return true; } std::vector> pairwiseGrouping( const std::vector& words ) { std::vector> groups; for (const std::string& word : words) { bool placed = false; for (auto& group : groups) { if (!haveSameFrequency(word, group.front())) continue; group.push_back(word); placed = true; break; } if (!placed) groups.push_back({word}); } return groups; } std::vector> sortedSignatureGrouping( const std::vector& words ) { std::unordered_map groupIndex; std::vector> groups; for (const std::string& word : words) { std::string signature = word; std::sort(signature.begin(), signature.end()); auto [it, inserted] = groupIndex.emplace( signature, static_cast(groups.size()) ); if (inserted) groups.push_back({}); groups[it->second].push_back(word); } return groups; } std::string buildFrequencySignature(const std::string& word) { std::array count{}; for (char ch : word) ++count[ch - 'a']; std::string signature; for (int frequency : count) { signature.push_back('#'); signature += std::to_string(frequency); } return signature; } std::vector> frequencySignatureGrouping( const std::vector& words ) { std::unordered_map groupIndex; std::vector> groups; for (const std::string& word : words) { std::string signature = buildFrequencySignature(word); auto [it, inserted] = groupIndex.emplace( std::move(signature), static_cast(groups.size()) ); if (inserted) groups.push_back({}); groups[it->second].push_back(word); } return groups; } public: std::vector> groupAnagrams( std::vector& strs ) { return frequencySignatureGrouping(strs); } }; 题解 ---- 逐组比较基线 ~~~~~~~~~~~~ 最直接的做法是维护已经建立的分组。处理新字符串时,把它依次与每组的代表字符串比较;字符频次相同就加入该组, 所有组都不匹配时再新建一组。 代表字符串足以判断组别。异位词关系只取决于 26 种字符的出现次数,同一组中的字符串都与代表具有相同频次, 因此彼此也具有相同频次。 ``pairwiseGrouping`` 正确地保留了每个输入元素,但会反复计算频次。若已经形成 ``g`` 个组,新字符串最坏需要执行 ``g`` 次比较;当大部分字符串互不相同时,组数接近字符串数量,整体退化为平方级。 从比较到签名 ~~~~~~~~~~~~ 逐组比较反复询问“当前字符串与这个代表是否同组”。可以改为给每个字符串计算一次规范签名,并要求: .. code-block:: text 两个字符串互为异位词 <=> 两个签名完全相同 签名相同的字符串直接进入同一哈希桶,不再逐个尝试已有代表。算法的核心因此从两两判定变成构造能够完整表示字符 多重集合的键。 排序签名 ~~~~~~~~ 把字符串中的字符排序,排列顺序被消除。例如: .. code-block:: text arc -> acr car -> acr rat -> art 异位词拥有相同字符及次数,排序结果必然相同;排序结果相同也说明每个字符及其次数完全一致。因此排序后的字符串是 异位词类别的充要签名。 ``sortedSignatureGrouping`` 对每个字符串生成排序副本,再通过哈希表找到对应组。该方法简单,并且适用于字符集合不固定 的情况;长度为 ``k`` 的字符串需要 ``O(k log k)`` 时间生成签名。 频次签名 ~~~~~~~~ 本题字符集合固定为 26 个小写字母,可以直接使用频次数组: .. code-block:: text count[0] 记录 a 的数量 count[1] 记录 b 的数量 ... count[25] 记录 z 的数量 两个字符串互为异位词,当且仅当 26 个分量逐项相等。生成频次只需扫描字符串,不再需要排序。 代码把频次数组序列化为字符串键。每个分量前加入 ``#`` 分隔符: .. code-block:: text [1, 11, 0, ...] -> #1#11#0... [11, 1, 0, ...] -> #11#1#0... 分隔符保留了每个计数的边界;若直接连接十进制数字,``[1, 11]`` 与 ``[11, 1]`` 都可能变成 ``111``,从而把 不同频次向量错误地放入同一组。 签名分桶不变量 ~~~~~~~~~~~~~~ ``groupIndex[signature]`` 保存该签名对应的结果组下标。处理每个字符串时保持以下状态: * ``groups`` 已经包含所有处理过的字符串,并且每个字符串恰好出现一次; * ``groupIndex`` 中每个签名只对应一个组; * 同一组中的字符串具有相同签名,不同组的签名不同。 首次看到某个签名时,在 ``groups`` 末尾建立新组,并登记它的下标;以后相同签名直接追加到原组。由于签名与字符 频次一一对应,同组字符串必然互为异位词,不同组至少有一个频次分量不同。 外层循环对每个输入字符串执行一次追加,因此不会遗漏或额外复制。相同字符串在输入中重复出现时,每次都会再次追加, 原有重复次数也被完整保留。空字符串的 26 项计数全为零,同样拥有唯一签名。 状态演化 ~~~~~~~~ 处理 ``["eat", "tea", "tan", "ate", ""]`` 时: .. list-table:: :header-rows: 1 * - 字符串 - 签名关系 - 操作 * - ``eat`` - 首次出现 - 建立组 0,加入 ``eat`` * - ``tea`` - 与 ``eat`` 相同 - 加入组 0 * - ``tan`` - 首次出现 - 建立组 1,加入 ``tan`` * - ``ate`` - 与 ``eat`` 相同 - 加入组 0 * - 空字符串 - 26 项全为 0 - 建立组 2 哈希表只保存组下标,结果数组可以在读取输入时直接构造,也不依赖哈希表最终的遍历顺序。 代码演进 ~~~~~~~~ ``pairwiseGrouping`` 逐组寻找代表,逻辑直接,但相同频次被重复计算。 ``sortedSignatureGrouping`` 为每个字符串建立排序规范键,把逐组搜索改为一次哈希查询。 ``frequencySignatureGrouping`` 利用固定字符集合,以线性扫描生成频次签名。公开入口采用该方法,因为它避免了每个字符串 内部的排序。 复杂度分析 ~~~~~~~~~~ 设字符串数量为 ``n``,总字符数为 ``C``,最长字符串长度为 ``k``。 逐组比较在组数接近 ``n`` 时需要 ``O(n^2 k)`` 时间。排序签名方法需要 ``O(sum(len(word) log len(word)))`` 时间,可粗略写成 ``O(nk log k)``。 频次签名扫描全部字符需要 ``O(C)``,每个字符串还要序列化固定的 26 个计数,因此总时间为 ``O(C + n)``。 不计返回结果中的字符串存储,哈希键和组索引使用 ``O(n)`` 额外空间;26 维计数属于常量空间。