The solution of Repeated String Match is relatively simple:
object Solution
// time: complexity to find `b_len` string in `a_len + b_len` string
// O(b_len * (a_len + b_len))
// space: O(a_len + b_len)
def repeatedStringMatch(a: String, b: String): Int =
val repeatCount = (b.length + a.length - 1) / a.length
val aRepeated = a * repeatCount
if (aRepeated.contains(b))
repeatCount
else if ((aRepeated + a).contains(b))
repeatCount + 1
else
-1
The next thing I’d like to know is that if the current solution with string
multiplication is slower than the one with StringBuilder
. My first attempt
is as follows:
import scala.annotation.tailrec
object Solution
def repeatedStringMatch(a: String, b: String): Int =
val repeatCount = (b.length + a.length - 1) / a.length
@tailrec
def loop(sb: StringBuilder = new StringBuilder): StringBuilder =
if (sb.length >= b.length)
sb
else
loop(sb.append(a))
val sb = loop()
if (sb.contains(b))
repeatCount
else if (sb.append(a).contains(b))
repeatCount + 1
else
-1
It compiles but gives the incorrect answer. Why? You might notice that
StringBuilder
calls contains
. It would cause a compilation error in Java
because StringBuilder
doesn’t have this method. The explanation is that the
contains
is not one that I think.
StringBuilder
in Scala is
derived
from AbstractSeq[Char]
. AbstractSeq[Char]
has the polymorphic method
contains
defined as:
def contains[A1 >: A](elem: A1): Boolean = exists (_ == elem)
Where A
is Char
for a StringBuilder
. If StringBuilder
calls
contains("a")
, then the compiler infers A1
to the least common supertype
of Char
and String
which is Any
. With Any
and AnyVal
, such a call
would never cause a compilation error with any argument given to contains
:
@ val sb = new StringBuilder("abc")
sb: StringBuilder = IndexedSeq('a', 'b', 'c')
@ sb.contains("a")
res1: Boolean = false
@ sb.contains(1)
res2: Boolean = false
Moreover, the problem is well known and much broader as I found out from the community.
The funny thing is that Int
is a supertype of Char
, that causes
@ sb.contains(97)
res3: Boolean = true
Finally, the correct code is as follows:
import scala.annotation.tailrec
object Solution
def repeatedStringMatch(a: String, b: String): Int =
val repeatCount = (b.length + a.length - 1) / a.length
@tailrec
def loop(sb: StringBuilder = new StringBuilder): StringBuilder =
if (sb.length >= b.length)
sb
else
loop(sb.append(a))
val sb = loop()
if (sb.toString.contains(b))
repeatCount
else if (sb.append(a).toString.contains(b))
repeatCount + 1
else
-1