在Char迭代器中查找字符串

我有一個用例，我需要從Char的迭代器中返回一個字符串到分隔符字符串（如果找到）。在Char迭代器中查找字符串

合同：

如果迭代器被耗盡（僅在開始），返回None
如果分隔符字符串被發現，才返回全部字符（空字符串是罰款），分隔符會被丟棄
否則返回其餘字符
不要急於耗盡迭代器！

我確實有這個有效的解決方案，但感覺像Java（這是我來自）

class MyClass(str: String) { 
    def nextString(iterator: Iterator[Char]): Option[String] = { 
    val sb = new StringBuilder 
    if(!iterator.hasNext) return None 
    while (iterator.hasNext) { 
     sb.append(iterator.next()) 
     if (sb.endsWith(str)) return Some(sb.stripSuffix(str)) 
    } 
    Some(sb.toString()) 
    } 
}

有沒有一種方法，我可以在一個功能更強大的方式做到這一點（理想情況下不改變方法簽名）？

更新：這是我如何測試這個

val desmurfer = new MyClass("_smurf_") 
val iterator: Iterator[Char] = "Scala_smurf_is_smurf_great_smurf__smurf_".iterator 
println(desmurfer.nextString(iterator)) 
println(desmurfer.nextString(iterator)) 
println(desmurfer.nextString(iterator)) 
println(desmurfer.nextString(iterator)) 
println(desmurfer.nextString(iterator)) 
println 
println(desmurfer.nextString("FooBarBaz".iterator)) 
println(desmurfer.nextString("".iterator))

輸出：

Some(Scala) 
Some(is) 
Some(great) 
Some() 
None 

Some(FooBarBaz) 
None

來源

2015-12-18 Sean Patrick Floyd

您期望的示例輸出是什麼？ –

@ S.Karthik添加樣例輸出 –

請檢查答案 –

一位同事提供了這樣的回答，這是他原來的做法，並從我身邊一些拋光之間的混合的氣質。謝謝，埃文斯！然後另一位同事也添加了一些輸入。由於赤穗:-)

class MyClass(str: String) { 
    def nextString(iterator: Iterator[Char]): Option[String] = { 

    def nextString(iterator: Iterator[Char], sb: StringBuilder): Option[String] = { 
     if (!iterator.hasNext || sb.endsWith(str)) { 
     Some(sb.stripSuffix(str)) 
     } else { 
     nextString(iterator, sb.append(iterator.next())) 
     } 
    } 

    if (!iterator.hasNext) None 
    else nextString(iterator, new StringBuilder) 
    } 
}

到目前爲止，我喜歡這種方法，最好的，所以我會接受它在兩天內，除非有一個更好的答案，屆時。

來源

2015-12-18 15:10:07

你應該把它變成一個迭代器本身。 'MyIterator類（迭代器：Iterator [Char]）擴展Iterator {def hasNext（）= iterator.hasNext; def next（）= {<你的nextString的主體，主要是>）}' –

更新時間：此作品，未經迭代器轉換爲字符串

def nextString(iterator: Iterator[Char]): Option[String] = { 
    if (iterator.isEmpty) None 
    else Some(iterator.foldLeft("") { (result, currentChar) => if (res.endsWith(str)) result else result + currentChar}) 
}

來源

2015-12-18 10:16:06 James

如果我被允許轉換爲字符串，答案將是顯而易見的。我的約束是我應該只根據需要採取儘可能多的字符（添加到合同） –

我錯過了那部分。我已經更新了我的答案，但沒有將迭代器轉換爲字符串 – James

'foldLeft'仍然消耗整個迭代器。 – Haspemulator

這個怎麼樣一個：

scala> def nextString(itr: Iterator[Char], sep: String): Option[String] = { 
    | def next(res: String): String = 
    |  if(res endsWith sep) res dropRight sep.size else if(itr.hasNext) next(res:+itr.next) else res 
    | if(itr.hasNext) Some(next("")) else None 
    | } 
nextString: (itr: Iterator[Char], sep: String)Option[String] 

scala> val iterator: Iterator[Char] = "Scala_smurf_is_smurf_great".iterator 
iterator: Iterator[Char] = non-empty iterator 

scala> println(nextString(iterator, "_smurf_")) 
Some(Scala) 

scala> println(nextString(iterator, "_smurf_")) 
Some(is) 

scala> println(nextString(iterator, "_smurf_")) 
Some(great) 

scala> println(nextString(iterator, "_smurf_")) 
None 

scala> println(nextString("FooBarBaz".iterator, "_smurf_")) 
Some(FooBarBaz)

來源

2015-12-18 10:58:58 Eastsun

這很好，但我猜'：+'應該是O（n），並且在有很多通話的情況下也有內存問題。請看我的答案（儘管更大更大），因爲我嘗試改進。你的答案仍然可能會更好，因爲簡單 – Archeg

這似乎是在做你想做的事。 @Eastsun回答動機我

val str = "hello" 

    def nextString2(iterator: Iterator[Char]): Option[String] = { 
    val maxSize = str.size 
    @tailrec 
    def inner(collected: List[Char], queue: Queue[Char]): Option[List[Char]] = 
     if (queue.size == maxSize && queue.sameElements(str)) 
     Some(collected.reverse.dropRight(maxSize)) 
     else 
     iterator.find(x => true) match { 
      case Some(el) => inner(el :: collected, if (queue.size == maxSize) queue.dequeue._2.enqueue(el) else queue.enqueue(el)) 
      case None => Some(collected.reverse) 
     } 

    if (iterator.hasNext) 
     inner(Nil, Queue.empty).map(_.mkString) 
    else 
     None 
    } 

    test(nextString2(Nil.iterator)) === None 
    test(nextString2("".iterator)) === None 
    test(nextString2("asd".iterator)) === Some("asd") 
    test(nextString2("asfhello".iterator)) === Some("asf") 
    test(nextString2("asehelloasdasd".iterator)) === Some("ase")

但我真的認爲它太複雜，無法使用。有時你必須在scala中使用非FP的東西來提高性能。

P.S.我不知道如何在它的第一個元素上匹配迭代器，所以我使用了醜陋的iterator.find(x => true)。抱歉。

P.P.S.一點解釋。我不經意地建立了collected來填補你正在尋找的元素。我還建立queue與最後str.size - 元素。然後我每次只檢查str這個隊列。這可能不是做這件事的最有效的方法。如果你想要更多，你可以使用Aho-Corasick算法或模擬。

P.P.P.S.並且我使用iterator作爲狀態，這可能不是FP方式

P.P.P.P.S.你測試通過，以及：

val desmurfer = new MyClass("_smurf_") 
    val iterator: Iterator[Char] = "Scala_smurf_is_smurf_great".iterator 
    test(desmurfer.nextString2(iterator)) === Some("Scala") 
    test(desmurfer.nextString2(iterator)) === Some("is") 
    test(desmurfer.nextString2(iterator)) === Some("great") 
    test(desmurfer.nextString2(iterator)) === None 
    println() 
    test(desmurfer.nextString2("FooBarBaz".iterator)) === Some("FooBarBaz") 
    test(desmurfer.nextString2("".iterator)) === None

來源

2015-12-18 11:47:04 Archeg

這裏有一個我張貼只是因爲它是一個有點扭曲:)我不會真的建議使用它：

class MyClass2(str: String) { 
    val sepLength = str.length 
    def nextString(iterator: Iterator[Char]): Option[String] = { 
     if (!iterator.hasNext) return None 

     val sit = iterator.sliding(sepLength) 
     val prefix = sit.takeWhile(_.mkString != str).toList 

     val prefixString = prefix.toList.map(_.head).mkString 
     if (prefix.head.length < sepLength) Some(prefix.head.mkString) 
     else if (!iterator.hasNext) Some(prefix.head.mkString + prefix.last.mkString) 
     else Some(prefixString) 

    } 
    }

的想法是，通過調用sliding()在我們的基礎迭代器上，我們可以得到一個序列，如果它存在的話，其中一個將是我們的分隔符。所以我們可以使用takeWhile找到分隔符。然後，在我們的分隔符之前的每個滑動字符串的第一個字符是我們跳過的字符串。正如我所說，翹曲。

我很喜歡sliding被定義爲使得它產生長度n和在長度n-1，n-2 .... 1的這個特定使用情況下，結束序列的所有子序列，但它沒有和可怕的if語句最後是處理各種情況。

它通過測試用例:)

來源

2015-12-18 13:56:20

我很喜歡這個迄今爲止最好的。也看了一下.sliding，但後來拒絕它太複雜了。 –

在邊界情況下，分隔符是底層迭代器中的最後一件事或第一件事。在這種情況下，它會混亂起來。我可能會後來解決這個問題。你可能需要更多的測試用例... –

這個呢？

def nextString(iterator: Iterator[Char]): Option[String] = { 
    val t = iterator.toStream 

    val index = t.indexOfSlice(s) 
    if(t.isEmpty) None 
    else if(index == -1) Some(t.mkString) 
    else Some(t.slice(0,index).mkString) 
    }

它通過這個測試：

val desmurfer = new MyClass("_smurf_") 
val iterator: Iterator[Char] = "Scala_smurf_is_smurf_great_smurf__smurf_".iterator 
assert(desmurfer.nextString(iterator) == Some("Scala")) 
assert(desmurfer.nextString(iterator) == Some("is")) 
assert(desmurfer.nextString(iterator) == Some("great")) 
assert(desmurfer.nextString(iterator) == Some("")) 
assert(desmurfer.nextString(iterator) == None) 

assert(desmurfer.nextString("FooBarBaz".iterator) == Some("FooBarBaz")) 
assert(desmurfer.nextString("".iterator) == None)

更新：去除「指標== -1 & &」從最初的「如果條件條款」。

來源

2015-12-19 14:06:07 nikiforo

是的，我喜歡它 –

非常好。只是好奇：爲什麼測試兩次'索引'？ 't.isEmpty'可能同時'index！= -1'嗎？ – jwvh

@jwvh是的，謝謝，那個檢查不需要:) – nikiforo

在Char迭代器中查找字符串

回答

相關問題