Разделение строки на группы

Ответ 1

Вы можете разбить строку рекурсивно на span:

def s(x : String) : List[String] = if(x.size == 0) Nil else {
    val (l,r) = x.span(_ == x(0))
    l :: s(r) 
}

Рекурсивный хвост:

@annotation.tailrec def s(x : String, y : List[String] = Nil) : List[String] = {
    if(x.size == 0) y.reverse 
    else {
        val (l,r) = x.span(_ == x(0))
        s(r, l :: y)
    }
}

Ответ 2

Кажется, что все другие ответы очень сосредоточены на операциях по сбору. Но решение pure + regex намного проще:

str split """(?<=(\w))(?!\1)""" toList

В этом регулярном выражении я использую положительный lookbehind и негативный просмотр для захваченного char

Ответ 3

def group(s: String): List[String] = s match {
  case "" => Nil
  case s  => s.takeWhile(_==s.head) :: group(s.dropWhile(_==s.head))
}

Изменить: Рекурсивная версия хвоста:

def group(s: String, result: List[String] = Nil): List[String] = s match {
  case "" => result reverse
  case s  => group(s.dropWhile(_==s.head), s.takeWhile(_==s.head) :: result)
}

может использоваться так же, как и у другого, потому что второй параметр имеет значение по умолчанию и, следовательно, не требуется.

Ответ 4

Сделайте его одним слоем:

scala>  val str = "aaaabbcddddeeeeefff"
str: java.lang.String = aaaabbcddddeeeeefff

scala> str.groupBy(identity).map(_._2)
res: scala.collection.immutable.Iterable[String] = List(eeeee, fff, aaaa, bb, c, dddd)

UPDATE

Поскольку @Paul упоминает о порядке здесь, обновленная версия:

scala> str.groupBy(identity).toList.sortBy(_._1).map(_._2)
res: List[String] = List(aaaa, bb, c, dddd, eeeee, fff)

Ответ 5

Вы можете использовать некоторые вспомогательные функции, например:

val str = "aaaabbcddddeeeeefff"

def zame(chars:List[Char]) = chars.partition(_==chars.head)

def q(chars:List[Char]):List[List[Char]] = chars match {
    case Nil => Nil
    case rest =>
        val (thesame,others) = zame(rest)
        thesame :: q(others)
}

q(str.toList) map (_.mkString)

Это должно сделать трюк, верно? Несомненно, он может быть очищен в однострочном пространстве еще больше

Ответ 6

Функциональное * решение с использованием fold:

def group(s : String) : Seq[String] = {
  s.tail.foldLeft(Seq(s.head.toString)) { case (carry, elem) =>
    if ( carry.last(0) == elem ) {
      carry.init :+ (carry.last + elem)
    }
    else {
      carry :+ elem.toString
    }
  }
}

Существует много затрат, скрытых во всех тех операциях последовательности, которые выполняются в строках (через неявное преобразование). Я предполагаю, что реальная сложность сильно зависит от типа строк Seq, которые преобразуются в.

(*) Afaik все/большинство операций в библиотеке коллекций зависят от итераторов, имхо по своей сути нефункциональной концепции. Но код выглядит функционально, по крайней мере.

Ответ 7

Изменить: Придется читать более внимательно. Ниже нет функционального кода.

Иногда, небольшое изменяемое состояние помогает:

def group(s : String) = {
  var tmp = ""
  val b = Seq.newBuilder[String]

  s.foreach { c =>
    if ( tmp != "" && tmp.head != c ) {
      b += tmp
      tmp = ""
    }

    tmp += c
  }
  b += tmp

  b.result
}

Время выполнения O (n) (если сегменты имеют не более постоянной длины), а tmp.+=, вероятно, создает наибольшие издержки. Вместо строкового исполнения используйте строковый построитель в O (n).

group("aaaabbcddeeeeeeffg")
> Seq[String] = List(aaaa, bb, c, dd, eeeeee, ff, g)

Ответ 8

Начиная с Scala 2.13, List теперь поставляется с компоновщиком Option[(A,S)]):CC[A] rel="nofollow noreferrer"> unfold который можно комбинировать с Boolean):(String,String) rel="nofollow noreferrer"> String::span:

List.unfold("aaaabbaaacdeeffg") {
  case ""   => None
  case rest => Some(rest.span(_ == rest.head))
}
// List[String] = List("aaaa", "bb", "aaa", "c", "d", "ee", "ff", "g")

или, в качестве альтернативы, в сочетании с Scala 2.13 A):Option[A] rel="nofollow noreferrer"> Option#unless:

List.unfold("aaaabbaaacdeeffg") {
  rest => Option.unless(rest.isEmpty)(rest.span(_ == rest.head))
}
// List[String] = List("aaaa", "bb", "aaa", "c", "d", "ee", "ff", "g")

Подробности:

• Развернуть (def unfold[A, S](init: S)(f: (S) ⇒ Option[(A, S)]): List[A]) основан на внутреннем состоянии (init), которое инициализируется в нашем случай с "aaaabbaaacdeeffg".
• Для каждой итерации мы span (def span(p: (Char) ⇒ Boolean): (String, String)) это внутреннее состояние, чтобы найти префикс, содержащий тот же символ, и создать кортеж (String, String) который содержит префикс и остальная часть строки. В этом контексте span очень удачен, так как он производит именно то, что ожидает unfold: кортеж, содержащий следующий элемент списка и новое внутреннее состояние.
• Развертывание прекращается, когда внутреннее состояние равно "" в этом случае мы создаем None как ожидается при разворачивании для выхода.

Ответ 9

Если вы хотите использовать Scala API, вы можете использовать встроенную функцию для этого:

str.groupBy(c => c).values

Или, если вы не возражаете против сортировки и в списке:

str.groupBy(c => c).values.toList.sorted