CODEWITHSUNDEEP
scalafunctional-programming
TriCore
TriCore

Reputation: 1914

Implement an algorithm in Scala to determin if a string has all unique characters

I am solving trivial problems to learn Scala. Here is what I have come up with

def isUnique(str: String): Boolean = {
    if (str.length > 128) return false
    val uniqueChars = new Array[Boolean](128)

    !(str.map(c => addChar(c, uniqueChars)).find(identity).isDefined)
}

def addChar(ch: Char, uniqueChars: Array[Boolean]): Boolean = {
    if (uniqueChars(ch)) return true else {
    uniqueChars(ch) = true;
    return false
}

Is that it?

Please note that I don't care about the logic or optimization at this point. I only need to learn the Scala way of doing it.

[Edit] Let's assume we don't want to use the string distinct method. I only need to verify the functional style of Scala.

Upvotes: 1

Views: 321

Answers (2)

jwvh
jwvh

Reputation: 51271

OK, so if you don't to want utilize the distinct library method then recursion is usually the functional way to go.

def isUnique(str: String, chrs: Set[Char] = Set()): Boolean =
  str.length == 0 ||
    !chrs(str.head) &&
      isUnique(str.tail, chrs + str.head)

isUnique("abcdexf")  // true
isUnique("abcdxxf")  // false
isUnique("fbcdexf")  // false
isUnique("abdbexf")  // false

Upvotes: 5

Dima
Dima

Reputation: 40500

You want to "learn scala way of doing it", by actually doing it in a way, that makes no sense to use in scala? Scala way of doing it str == str.distinct. If "you don't want to use distinct", then str.toSet.size == str.length. If you don't want toSet either, then str.groupBy(identity).values.map(_.size).forall(_ == 1). If you don't want .groupBy then str.sorted.sliding(2).forall(s => s.head != s.last)

Etc. ... At some point, "scala way" just stops being "scala way" and becomes a java program written in scala syntax.

Upvotes: -3

Related Questions