Written by Amit Bansal
on April 24, 2018

LeetCode Problem: 49. Group Anagrams

Problem description can be found here
So in this problem we need to group all the anagrams together. Here is a scala solution:

object Solution {
  def groupAnagrams(strs: Array[String]): List[List[String]] = {
    def solve(strs: Array[String],
              idx: Int,
              mp: Map[String, List[String]]): Map[String, List[String]] = {
      if (idx >= strs.size) mp
      else {
        val str = strs(idx).sortWith(_ < _)
        mp.get(str) match {
          case Some(xs: List[String]) =>
            solve(strs, idx + 1, mp.updated(str, xs :+ strs(idx)))
          case _ => solve(strs, idx + 1, mp + (str -> List(strs(idx))))
        }
      }
    }
    solve(strs, 0, Map[String, List[String]]()).values.toList
  }
}

In this solution we are recursively traversing over all the strings and appending it to the value in a map. Where key is string sorted version of the same string. So after after the method call to solve. Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"] We will have a map that looks like this.

{
  "aet":["ate","eat","tea"]
  "ant":["nat","tan"]
  "abt":["bat"]
}

Now all we need to do is extract only values for all keys. which can be done using this .values.toList So here is our solution.

Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

With some clever use of Scala api we can also do something like this:

object Solution {
  def groupAnagrams(strs: Array[String]): List[List[String]] = {
    strs.groupBy(_.sorted).values.map(_.toList).toList
  }
}

So apparently in the previous solution we are implementing a version of groupBy method.

← → Top