字母异位词分组

核心思想

字母异位词的特点是，它们的字母组成相同，只是排列顺序不同。因此，可以通过对每个字符串进行排序，将排序后的字符串作为键，将原始字符串作为值存入哈希表中。最后，将哈希表中的值提取出来，即为分组后的结果。

具体步骤

排序法：

• 遍历字符串数组，对每个字符串进行排序，将排序后的字符串作为键，原始字符串作为值存入哈希表。
• 最后，将哈希表中的值提取出来，即为分组后的结果。

复杂度分析

• 时间复杂度：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)); // 输出分组结果 
        }
    }
} 

Leetcode 2.字母异味词分组-原题链接

题目内容

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序输出结果列表。

字母异位词是由重新排列源单词的所有字母得到的一个新单词。

输入描述

输入共两行。

• 第一行一个整数$n$，代表字符串数组长度。
• 第二行有$n$个字符串，代表字符串数组，字符串之间以空格分隔。

输出描述

输出结果列表，每一行表示一组。 每一组的字符串以空格分隔。

样例1

输入

6
eat tea tan ate nat bat

输出

bat
nat tan
ate eat tea

样例2

输入

1
a

输出

a

提示

• $1 <= strs.length <= 10^4$
• $0 <= strs[i].length <= 100$
• $strs[i]$仅包含小写字母