LeetCode 算法： 字母异位词分组c++

本文主要是介绍LeetCode 算法： 字母异位词分组c++，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接🔗：字母异位词分组
难度：中等⭐️⭐️

题目

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
示例 2:

输入: strs = [“”]
输出: [[“”]]
示例 3:

输入: strs = [“a”]
输出: [[“a”]]

提示：

1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

字母异位词

字母异位词（Anagrams）是指由相同数量的字母组成，但字母的排列顺序不同的单词。例如，“listen” 和 “silent” 就是一对字母异位词，因为它们包含相同的字母，只是排列顺序不同。

在编程中，解决字母异位词问题通常涉及到以下几个步骤：

• 排序：将每个单词的字母排序，因为字母异位词排序后会得到相同的字符序列。
• 映射：使用排序后的字符串作为键，将原始单词作为值存储在映射（如哈希表）中。
• 分组：将映射中的值（即具有相同排序字符串的单词列表）提取出来，形成字母异位词的分组

题解

排序法

1. 解题思路：
   • 由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。
   • 在C++中，你可以使用 std::sort 函数对字符串进行排序，然后使用 std::unordered_map 来实现映射和分组。
2. 复杂度：时间复杂度O(nklog⁡k)，空间复杂度O(nk)
3. 代码流程：
   • 定义了一个Solution类，它包含了groupAnagrams函数。这个函数接收一个字符串数组strs，并返回一个字符串数组的数组，表示字母异位词的分组。
   • 使用了一个unordered_map来存储排序后的字符串作为键，以及一个包含原始字符串的向量作为值。对于输入数组中的每个字符串，我们首先将其排序，然后将其添加到对应排序字符串键的值向量中。
   • 最后，我们将unordered_map中的所有值向量添加到结果数组result中，并返回这个数组。
4. c++ demo：

#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <unordered_map>class Solution {
public:std::vector<std::vector<std::string>> groupAnagrams(std::vector<std::string>& strs) {std::vector<std::vector<std::string>> result;std::unordered_map<std::string, std::vector<std::string>> anagramMap;// 对每个字符串进行排序并生成keyfor (const std::string& str : strs) {std::string sortedStr = str;std::sort(sortedStr.begin(), sortedStr.end());anagramMap[sortedStr].push_back(str);}// 将anagramMap中的值（即异位词组）添加到结果中for (const auto& pair : anagramMap) {result.push_back(pair.second);}return result;}
};int main() {Solution solution;std::vector<std::string> strs = { "eat", "tea", "tan", "ate", "nat", "bat" };std::vector<std::vector<std::string>> groupedAnagrams = solution.groupAnagrams(strs);// 打印结果for (const auto& group : groupedAnagrams) {for (const std::string& word : group) {std::cout << word << " ";}std::cout << std::endl;}return 0;
}

输出结果：

eat tea ate
tan nat
bat

这篇关于LeetCode 算法： 字母异位词分组c++的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---