分割字符串成组

我想“组”字符串成段，我想这个例子就是说明它更succintly分割字符串成组

scala> val str: String = "aaaabbcddeeeeeeffg" 
... (do something) 
res0: List("aaaa","bb","c","dd","eeeee","ff","g")

我可以thnk的几种方法在命令式风格要做到这一点（与vars和逐句通过字符串查找组），但我想知道是否有更好的功能解决方案可以达到？我一直在浏览Scala API，但似乎并不符合我的需求。

任何帮助，将不胜感激

来源

2011-03-09 djhworld

如果你想提及（和标记）你想工作的语言，这将是有帮助的！ – 2011-03-09 15:35:02

该帖子已被标记？可能需要一段时间才能出现在SO服务器上 – djhworld 2011-03-09 15:46:40

您是否期望匹配'aaabbccddeeffffffhhhhhiiiiijjjj'等？或者只是那7个字符？ – OscarRyz 2011-03-09 16:12:39

你可以用递归跨度分割字符串：

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

来源

2011-03-09 16:03:27

可能条件可能会被表达为匹配吗？ – 2011-03-09 16:41:05

@保罗 - 不，我不这么认为。这场比赛需要更多的空间，并且对比大小的检查非常清楚。 @Thomas - 看到我对Martin Ring的回答的评论。我喜欢这个答案，但我想指出这种方法的缺点。 – 2011-03-09 17:37:32

@Paul你可以像Martin一样执行它。我其实这样做，但它不是更可读。 – 2011-03-09 18:00:33

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

可用于就像其他因为第二参数具有缺省值，从而不必须被提供。

来源

2011-03-09 16:10:34

@Rex Kerr为什么会是'O（n^2）'？我认为对于字符串的每个字符都有2个比较操作，这个操作并不是最优的（更好的解决方法是像托马斯所说的那样使用'span'），但是它仍然是'O（n）'？我错过了什么吗？ – 2011-03-09 17:42:13

@Rex我会说你每消耗一个角色一次（在这个实现中实际上可以两次）。这将是O（n）。（是的，你可以使它成为尾递归的，这是一个练习，不是问题。） – 2011-03-09 17:56:33

@Martin，@Thomas - 如果每个字符都不相同，则会生成平均长度为n/2的'n'字符串， O（n^2）'工作总数。 – 2011-03-09 19:11:54

你可以使用一些辅助功能，像这样：

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)

这应该做的伎俩，对不对？毫无疑问，它可以被清理成单行进一步

来源

2011-03-09 16:14:51 Anne

我想，分区并不能完成想要的任务。给定aaabbbbbaa它将返回aaaaa bbbbb – 2011-03-09 16:43:50

分区将列表拆分为两部分，因此将这样拆分为“aaaabbbbaaa”.toList将产生“aaaa”，“bbbbaaaaa”，然后以递归方式对列表的其余部分应用相同的函数。我认为它确实做到了你所需要的 – Anne 2011-03-10 08:36:13

分区不会在某一点分割列表。它收集所有匹配或不匹配谓词scala>“aaabbbbaaa”分区的所有元素（_ =='a'） res0：（String，String）=（aaaaaa，bbbb） scala>' – 2011-03-10 09:30:24

让它一行代码：

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：

正如@保罗提及这里的顺序更新的版本：

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

来源

2011-03-09 16:25:56

我认为从OP的例子中可以清楚地看到这些细分市场的顺序。 – 2011-03-09 16:44:51

@Paul订单没有提到反正我更新了代码 – 2011-03-09 16:57:05

这将导致'List（bb，aaa）'为'“aabba”'...不会吗？不知道这是否是djhworld想要的。 – 2011-03-09 17:26:02

编辑：必须更仔细地阅读。下面是没有功能的代码。

有时候，一个小可变的状态帮助：

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)

来源

2011-03-09 18:29:19 Raphael

如果在'collection.mutable.Seq'上有某种方法实际*修改了序列，则可以在tmp中使用一个双链表，并且在O（n）时间和内存中。 – Raphael 2011-03-09 18:42:32

似乎所有其他答案都非常集中于收集操作。但纯字符串+正则表达式的解决方案简单得多：

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

在这个表达式我使用正回顾后和功能*解决方案使用fold为拍摄焦炭

来源

2011-03-09 18:42:58 tenshi

+1 - 非常好！我总是忘记正则表达式的惊人力量。 – 2011-03-09 19:13:16

和惊人的不可读性。你真的可以说你没有仔细研究就明白这一点。 – 2011-03-09 19:32:27

这是“功能性”吗？ @保罗这是什么意见是 – Raphael 2011-03-09 20:02:00

负先行：

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集合库中的所有/大多数操作都依赖于迭代器，这是一种imho固有的不起作用的概念。但是代码至少看起来很实用。

来源

2011-03-09 20:05:50 Raphael

分割字符串成组

回答

相关问题