comments | edit_url |
---|---|
true |
给定一个字符串数组 strs
,将 变位词 组合在一起。 可以按任意顺序返回结果列表。
注意:若两个字符串中每个字符出现的次数都相同且字符顺序不完全相同,则称它们互为变位词。
示例 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]
仅包含小写字母
注意:本题与主站 49 题相同: https://leetcode.cn/problems/group-anagrams/
- 遍历字符串,对每个字符串按照字符字典序排序,得到一个新的字符串。
- 以新字符串为
key
,[str]
为value
,存入哈希表当中(HashMap<String, List<String>>
)。 - 后续遍历得到相同
key
时,将其加入到对应的value
当中即可。
以 strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
为例,遍历结束时,哈希表的状况:
key | value |
---|---|
"aet" |
["eat", "tea", "ate"] |
"ant" |
["tan", "nat"] |
"abt" |
["bat"] |
最后返回哈希表的 value
列表即可。
时间复杂度
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
d = defaultdict(list)
for s in strs:
k = ''.join(sorted(s))
d[k].append(s)
return list(d.values())
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> d = new HashMap<>();
for (String s : strs) {
char[] t = s.toCharArray();
Arrays.sort(t);
String k = String.valueOf(t);
d.computeIfAbsent(k, key -> new ArrayList<>()).add(s);
}
return new ArrayList<>(d.values());
}
}
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> d;
for (auto& s : strs) {
string k = s;
sort(k.begin(), k.end());
d[k].emplace_back(s);
}
vector<vector<string>> ans;
for (auto& [_, v] : d) ans.emplace_back(v);
return ans;
}
};
func groupAnagrams(strs []string) (ans [][]string) {
d := map[string][]string{}
for _, s := range strs {
t := []byte(s)
sort.Slice(t, func(i, j int) bool { return t[i] < t[j] })
k := string(t)
d[k] = append(d[k], s)
}
for _, v := range d {
ans = append(ans, v)
}
return
}
function groupAnagrams(strs: string[]): string[][] {
const d: Map<string, string[]> = new Map();
for (const s of strs) {
const k = s.split('').sort().join('');
if (!d.has(k)) {
d.set(k, []);
}
d.get(k)!.push(s);
}
return Array.from(d.values());
}
class Solution {
func groupAnagrams(_ strs: [String]) -> [[String]] {
var d = [String: [String]]()
for s in strs {
let sortedStr = String(s.sorted())
if d[sortedStr] == nil {
d[sortedStr] = [String]()
}
d[sortedStr]!.append(s)
}
return Array(d.values)
}
}
我们也可以将方法一中的排序部分改为计数,也就是说,将每个字符串 key
,将字符串 value
存入哈希表当中。
时间复杂度
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
d = defaultdict(list)
for s in strs:
cnt = [0] * 26
for c in s:
cnt[ord(c) - ord('a')] += 1
d[tuple(cnt)].append(s)
return list(d.values())
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> d = new HashMap<>();
for (String s : strs) {
int[] cnt = new int[26];
for (int i = 0; i < s.length(); ++i) {
++cnt[s.charAt(i) - 'a'];
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 26; ++i) {
if (cnt[i] > 0) {
sb.append((char) ('a' + i)).append(cnt[i]);
}
}
String k = sb.toString();
d.computeIfAbsent(k, key -> new ArrayList<>()).add(s);
}
return new ArrayList<>(d.values());
}
}
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> d;
for (auto& s : strs) {
int cnt[26] = {0};
for (auto& c : s) ++cnt[c - 'a'];
string k;
for (int i = 0; i < 26; ++i) {
if (cnt[i]) {
k += 'a' + i;
k += to_string(cnt[i]);
}
}
d[k].emplace_back(s);
}
vector<vector<string>> ans;
for (auto& [_, v] : d) ans.emplace_back(v);
return ans;
}
};
func groupAnagrams(strs []string) (ans [][]string) {
d := map[[26]int][]string{}
for _, s := range strs {
cnt := [26]int{}
for _, c := range s {
cnt[c-'a']++
}
d[cnt] = append(d[cnt], s)
}
for _, v := range d {
ans = append(ans, v)
}
return
}