#P4001. 字母异味词分组
-
ID: 2203
Tried: 370
Accepted: 126
Difficulty: 3
字母异味词分组
题目内容
给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序输出结果列表。
字母异位词是由重新排列源单词的所有字母得到的一个新单词。
输入描述
输入共两行。
- 第一行一个整数n，代表字符串数组长度。
- 第二行有n个字符串，代表字符串数组，字符串之间以空格分隔。
输出描述
输出结果列表，每一行表示一组。 每一组的字符串以空格分隔。
样例1
输入
6
eat tea tan ate nat bat
输出
bat
nat tan
ate eat tea
样例2
输入
1
a
输出
a
提示
- 1<=strs.length<=104
- 0<=strs[i].length<=100
- strs[i]仅包含小写字母
字母异位词分组
核心思想
字母异位词的特点是，它们的字母组成相同，只是排列顺序不同。因此，可以通过对每个字符串进行排序，将排序后的字符串作为键，将原始字符串作为值存入哈希表中。最后，将哈希表中的值提取出来，即为分组后的结果。
具体步骤
排序法：
- 遍历字符串数组，对每个字符串进行排序，将排序后的字符串作为键，原始字符串作为值存入哈希表。
- 最后，将哈希表中的值提取出来，即为分组后的结果。
复杂度分析
- 时间复杂度：
O(n * k log k)，其中n是字符串数组的长度，k是字符串的最大长度。排序每个字符串的时间复杂度为O(k log k)，遍历字符串数组的时间复杂度为O(n)。 - 空间复杂度：
O(n * k)，哈希表存储所有字符串。
代码实现
C++ 代码
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> mp; // 哈希表，键为排序后的字符串，值为原始字符串列表
for (string& str : strs) {
string key = str;
sort(key.begin(), key.end()); // 对字符串排序
mp[key].emplace_back(str); // 将原始字符串存入哈希表
}
vector<vector<string>> ans; // 结果列表
for (auto it = mp.begin(); it != mp.end(); ++it) {
ans.emplace_back(it->second); // 将哈希表中的值提取出来
}
return ans;
}
};
int main() {
int n;
cin >> n; // 输入字符串数组长度
vector<string> strs(n);
for (int i = 0; i < n; i++) {
cin >> strs[i]; // 输入字符串数组
}
Solution s;
auto ans = s.groupAnagrams(strs); // 调用分组函数
for (auto i : ans) {
for (auto j : i) cout << j << " "; // 输出分组结果
cout << endl;
}
return 0;
}
Python 代码
from collections import defaultdict
class Solution:
def groupAnagrams(self, strs):
mp = defaultdict(list) # 哈希表，键为排序后的字符串，值为原始字符串列表
for s in strs:
key = "".join(sorted(s)) # 对字符串排序
mp[key].append(s) # 将原始字符串存入哈希表
return list(mp.values()) # 返回哈希表中的值
if __name__ == "__main__":
n = int(input()) # 输入字符串数组长度
strs = input().split() # 输入字符串数组
solution = Solution()
ans = solution.groupAnagrams(strs) # 调用分组函数
for group in ans:
print(" ".join(group)) # 输出分组结果
Java 代码
import java.util.*;
public class Main {
public class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>(); // 哈希表，键为排序后的字符串，值为原始字符串列表
for (String s : strs) {
char[] charArray = s.toCharArray();
Arrays.sort(charArray); // 对字符串排序
String key = new String(charArray);
map.computeIfAbsent(key, k -> new ArrayList<>()).add(s); // 将原始字符串存入哈希表
}
return new ArrayList<>(map.values()); // 返回哈希表中的值
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 输入字符串数组长度
scanner.nextLine(); // 读取换行符
String[] strs = scanner.nextLine().split(" "); // 输入字符串数组
Main main = new Main();
Solution solution = main.new Solution();
List<List<String>> ans = solution.groupAnagrams(strs); // 调用分组函数
for (List<String> group : ans) {
System.out.println(String.join(" ", group)); // 输出分组结果
}
}
}