Как найти самый длинный общий префикс из двух строк в Scala?

Question

Как найти самый длинный общий префикс из двух строк в Scala?

Я, вероятно, могу кодировать «императивное» решение (с индексом i, работающим над строками, в то время как s(i) == t(i)), но я ищу решение «функционального стиля» (например, без явного обновления переменной индекса) ).

Answer 1

scala> "helloworld".zip("hellohell").takeWhile(Function.tupled(_ == _)).map(_._1).mkString
res130: String = hello

Answer 2

Еще одна рекурсивная версия.

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))
}

Это более чем в 10 раз быстрее, чем у sjj, и в два раза быстрее, чем у отсутствующих факторов substring в Java работает быстро, потому что String неизменен.

Answer 3

Рекурсивная версия:

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 4

Императивная версия может быть упрощена до

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);
}

Answer 5

Если скорость заключается в сделке, идти обязательно.

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

РЕДАКТИРОВАТЬ:

Согласно предложению Луиджи:

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 6

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 7

Чтобы получить общий префикс для любого числа строк:

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