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