分割字符串成組

我想「組」字符串成段，我想這個例子就是說明它更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

分割字符串成組

回答

相關問題