代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词,所有源单词中的字母通常恰好只用一次。
示例 1:
["eat", "tea", "tan", "ate", "nat", "bat"]
示例 2:
[""]
示例 3:
["a"]
提示:
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i]
仅包含小写字母方法一:哈希表
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
列表即可。
时间复杂度 $O(n\times k\times \log k)$。其中 $n$ 和 $k$ 分别是字符串数组的长度和字符串的最大长度。
方法二:计数
我们也可以将方法一中的排序部分改为计数,也就是说,将每个字符串 $s$ 中的字符以及出现的次数作为 key
,将字符串 $s$ 作为 value
存入哈希表当中。
时间复杂度 $O(n\times (k + C))$。其中 $n$ 和 $k$ 分别是字符串数组的长度和字符串的最大长度,而 $C$ 是字符集的大小,本题中 $C = 26$。
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:
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) {
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 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) {
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;
}
};
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[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
}
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
}
function groupAnagrams(strs: string[]): string[][] {
let map = new Map();
for (let str of strs) {
let arr = str.split('');
arr.sort();
let key = arr.join('');
let value = map.get(key) ? map.get(key) : [];
value.push(str);
map.set(key, value);
}
return Array.from(map.values());
}
function groupAnagrams(strs: string[]): string[][] {
const map = new Map<string, string[]>();
for (const str of strs) {
const k = str.split('').sort().join('');
map.set(k, (map.get(k) ?? []).concat([str]));
}
return [...map.values()];
}
use std::collections::HashMap;
impl Solution {
pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
let mut map = HashMap::new();
for s in strs {
let key = {
let mut arr = s.chars().collect::<Vec<char>>();
arr.sort();
arr.iter().collect::<String>()
};
let val = map.entry(key).or_insert(vec![]);
val.push(s);
}
map.into_iter().map(|(_, v)| v).collect()
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。