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

Question

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.

@jwvh Thanks... I wasn't aware of this method. Can you see my edit in the question? Lets assume we don't want to use distinct. — TriCore
– TriCore, Commented Jul 8, 2017 at 23:34

jwvh · Accepted Answer · 2017-07-09 13:41:38Z

5

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

edited Jul 9, 2017 at 13:41

answered Jul 9, 2017 at 0:11

jwvh

51.3k7 gold badges42 silver badges70 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

TriCore Over a year ago

Pretty slick! It took a min to get my head around this though. Thanks!

groromain92 Over a year ago

Since you're using sets, why not use str.toSet.size == str.size ?

jwvh Over a year ago

@RomainG; Since distinct had been rejected, and "functional style" requested, I thought that a demonstration of early termination via recursion might be what the OP was looking for.

Dima · Accepted Answer · 2017-07-09 02:07:54Z

-3

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.

edited Jul 9, 2017 at 2:07

answered Jul 9, 2017 at 2:02

Dima

40.6k6 gold badges54 silver badges80 bronze badges

1 Comment

TriCore Over a year ago

I don't want to make it Java. I wanted to know how would you implement distinct method in Scala. I am sure its not implemented using Java or groupBy or sorting. Please also see the accepted answer above. (FYI, I didn't down vote your answer).

Collectives™ on Stack Overflow

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

2 Answers 2

3 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related