本文主要是介绍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” 就是一对字母异位词,因为它们包含相同的字母,只是排列顺序不同。
在编程中,解决字母异位词问题通常涉及到以下几个步骤:
- 排序:将每个单词的字母排序,因为字母异位词排序后会得到相同的字符序列。
- 映射:使用排序后的字符串作为键,将原始单词作为值存储在映射(如哈希表)中。
- 分组:将映射中的值(即具有相同排序字符串的单词列表)提取出来,形成字母异位词的分组
题解
排序法
- 解题思路:
- 由于互为字母异位词的两个字符串包含的字母相同,因此对两个字符串分别进行排序之后得到的字符串一定是相同的,故可以将排序之后的字符串作为哈希表的键。
- 在C++中,你可以使用 std::sort 函数对字符串进行排序,然后使用 std::unordered_map 来实现映射和分组。
- 复杂度:时间复杂度O(nklogk),空间复杂度O(nk)
- 代码流程:
- 定义了一个Solution类,它包含了groupAnagrams函数。这个函数接收一个字符串数组strs,并返回一个字符串数组的数组,表示字母异位词的分组。
- 使用了一个unordered_map来存储排序后的字符串作为键,以及一个包含原始字符串的向量作为值。对于输入数组中的每个字符串,我们首先将其排序,然后将其添加到对应排序字符串键的值向量中。
- 最后,我们将unordered_map中的所有值向量添加到结果数组result中,并返回这个数组。
- 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++的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!