LeetCode Entry

49. Group Anagrams

06.02.2024 medium 2024 kotlin rust

Group words by chars in them.

49. Group Anagrams medium blog post substack youtube image.png

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 sorting

  • Space 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()
  }