06.02.2024
49. Group Anagrams medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/497
Problem TLDR
Group words by chars in them.
Intuition
We can use char’s frequencies or just sorted words as keys to grouping.
Approach
Use the standard API for Kotlin and Rust:
groupBy vs no grouping method in Rust (but have in itertools)
entry().or_insert_with for Rust
keys are faster to just sort instead of count in Rust
Complexity
Time complexity:
O(mn), for counting, mlog(n) for sortingSpace complexity:
O(mn)
Code
fun groupAnagrams(strs: Array<String>): List<List<String>> =
strs.groupBy { it.groupBy { it } }.values.toList()
pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
let mut groups = HashMap::new();
for s in strs {
let mut key: Vec<_> = s.bytes().collect();
key.sort_unstable();
groups.entry(key).or_insert_with(Vec::new).push(s);
}
groups.into_values().collect()
}