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.

see https://stackoverflow.com/questions/22834018/scala-function-test-a-string-for-unique-char — frozen, Jul 08 '17 at 21:00
@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, Jul 08 '17 at 23:34

jwvh · Accepted Answer · 2017-07-09T13:41:38.093

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 09 '17 at 13:41

answered Jul 09 '17 at 00:11

jwvh

50,871
7
38
64

Pretty slick! It took a min to get my head around this though. Thanks! – TriCore Jul 09 '17 at 04:15
Since you're using sets, why not use `str.toSet.size == str.size` ? – groromain92 Dec 27 '19 at 10:52
@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. – jwvh Dec 27 '19 at 18:56

Dima · Answer 2 · 2017-07-09T02:07:54.953

-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 09 '17 at 02:07

answered Jul 09 '17 at 02:02

Dima

39,570
6
44
70

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). – TriCore Jul 09 '17 at 04:26

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

2 Answers2