0
\$\begingroup\$

Question is taken from leet code.

Problem

Given two strings s and t , write a function to determine if t is an anagram of s.

Examples

Input: s = "anagram", t = "nagaram"
Output: true

Input: s = "rat", t = "car"
Output: false

Here is my implementation in scala

import scala.collection.immutable.HashMap

object ValidAnagram extends App {
  def validAnagram(s1: String, s2: String): Boolean = {
    if (s1 == s2) true
    else if (s1.length != s2.length) false
    else {
      val lookupTable = s1.foldLeft(HashMap[Char,Int]()) ((m,c) => m ++ HashMap(c -> (if (m contains c) m(c) + 1 else 1)))
      println(lookupTable)
      (s2.foldLeft(lookupTable) {(m,c) =>
        if (m contains c) {
          val count = m(c)
          if (count > 1) {m + (c -> (count-1))} else m - c
        } else m  // we can return here if not functional
      }).isEmpty
    }
  }
    println(validAnagram(args(0), args(1)))
  }
\$\endgroup\$
  • \$\begingroup\$ I don't know Scala, so cannot provide a code review. But something seems complicated (creating hashmaps and then cycling through the maps). The easy way to determine if anagram - order s and order t (by whatever efficient way possible). If the s' and t' are the same, then is an anagram. \$\endgroup\$ – AJD Dec 1 '18 at 21:50
  • 1
    \$\begingroup\$ This is way too much code for such a basic task. If, for some reason, you don't want to sort the input before doing an equality check, you could build a Map equivalent of each input, i.e. val m1 = s1.groupBy(identity), and do the equality check on that: m1 == m2 \$\endgroup\$ – jwvh Dec 3 '18 at 8:34
  • \$\begingroup\$ Thanks for the comments. Problem is taken from an interview question site.. where you are supposed to touch upon time and space complexity of solutions for worst cases and then provide the optimal solution. Yes sorting is the easiest way of checking this. And I would use the same in production code if my input strings are not very very long. But as sorting may become expensive for larger string.. I chose going for populating a map. \$\endgroup\$ – vikrant Dec 4 '18 at 5:10
2
\$\begingroup\$

Short circuit!

Check the lengths first. In the case that they aren't the same, you don't need to incur a linear pass for an equality check.

Don't check the hashmap for an entry!

It's good that you know m(c) can throw if there's a missing key; luckily, you can use Map#getOrElse and provide a default -- in this case, it makes sense to provide a 0 default since you haven't seen the character.

Compare the counts from each string directly!

I find the subtracting of the counts to be very confusing. You'll need to remove keys from the counter if any of the values go to 0, which lowers the signal to noise ratio of the code. It's better to just build a second counter.


If you decide to build two counters and compare them, you'll need to do the same fold logic twice. This is really messy to write, so you won't want to do this twice. You may want to pimp out the String class. You can do this in the following way:

implicit class Counter(s: String) {
  def countCharacters: Map[Char, Int] = 
    s.foldLeft(Map.empty[Char, Int])({ case (acc, c) =>
      acc + (c -> (acc.getOrElse(c, 0) + 1))
    })
}

You can see it in action here:

scala> "hello".countCharacters
res0: Map[Char,Int] = Map(h -> 1, e -> 1, l -> 2, o -> 1)

So now you can compare the counts with a clean, non-repeated API.

Pulling this all together, you can write:

object ValidAnagram extends App {

  // when I see a string, implicitly construct a `Counter` instance
  implicit class Counter(s: String) {
    // this will be "added" to the String API via an implicit class construction
    def countCharacters: Map[Char, Int] = 
      s.foldLeft(Map.empty[Char, Int])({ case (acc, c) =>
        acc + (c -> (acc.getOrElse(c, 0) + 1))
      })
  }

  def validAnagram(s1: String, s2: String): Boolean =
    if (s1.length != s2.length) false
    else if (s1 == s2) true
    else s1.countCharacters == s2.countCharacters


  println(validAnagram(args(0), args(1)))
}
\$\endgroup\$
  • \$\begingroup\$ I really liked the ides of having an implicit for counter, it makes code very readable. \$\endgroup\$ – vikrant Dec 4 '18 at 5:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.