How to find the longest common prefix of two strin

Question

How to find the longest common prefix of two strings in Scala?

I probably can code an "imperative" solution (with an index i running over the strings while s(i) == t(i)) but I am looking for a "functional-style" solution (without updating the index variable explicitly, for instance).

Answer 1

Another recursive version.

def pref(s: String, t: String, out: String = ""): String = {
  if (s == "" || t == "" || s(0) != t(0)) out
  else pref(s.substring(1), t.substring(1), out + s(0))
}

It's over 10 times quicker than sjj's and over twice as fast as missingfaktor's. Java's substring is fast because String is immutable.

Answer 2

If speed is the deal, go imperative.

scala> def longestCommonPrefix(a: String, b: String): String = {
     |   var same = true
     |   val sb = new StringBuilder
     |   var i = 0
     |   while(same && i < math.min(a.length, b.length)) {
     |     if(a.charAt(i) != b.charAt(i)) {
     |       same = false
     |     } else {
     |       sb += a.charAt(i)
     |       i += 1
     |     }
     |   }
     |   sb.result
     | }
longestCommonPrefix: (a: String, b: String)String

scala> longestCommonPrefix("", "")
res50: String = ""

scala> longestCommonPrefix("helloworld", "hellohell")
res51: String = hello

EDIT:

As per Luigi's suggestion:

scala> def longestCommonPrefix(a: String, b: String): String = {
     |   var same = true
     |   var i = 0
     |   while(same && i < math.min(a.length, b.length)) {
     |     if(a.charAt(i) != b.charAt(i)) {
     |       same = false
     |     } else {
     |       i += 1
     |     }
     |   }
     |   a.substring(0, i)
     | }
longestCommonPrefix: (a: String, b: String)String

scala> longestCommonPrefix("helloworld", "hellohell")
res68: String = hello

Answer 3

def commonPrefix(strings: String*): String = {
  val refString = strings.map(s => (s, s.length())).minBy { case (string, length) => length }._1
  var i = 0
  while (i < refString.length) {
    if (!strings.forall(_(i) == refString(i))) return refString.substring(0, i)
    i += 1
  }
  return refString
}

Answer 4

To get the common prefix of any number of strings:

def commonPrefix (strs: Seq[String]): String = {
  var i = 0;
  strs(0).takeWhile { ch => strs.forall(_(i) == ch) && {i += 1; true}} mkString
} 

Answer 5

Recursive version:

def findCommonPrefix(s1 : String, s2 : String) : String = {
    def findCommonPrefixR(l1: List[Char], l2 : List[Char]) : List[Char] = {
        l1 match {
        case Nil => Nil
        case x::xs => if (l2 != Nil && l2.head == x) x :: findCommonPrefixR(xs, l2.tail) else Nil
        }
    }
    findCommonPrefixR(s1.toList, s2.toList).mkString
}

Answer 6

The imperative version can be simplified to

def longestCommonPrefix(s1:String, s2:String):String = {
  val maxSize = scala.math.min(s1.length, s2.length)
  var i:Int = 0;
  while ( i < maxSize && s1(i)== s2(i)) i += 1;
  s1.take(i);
}