scala - 更好的压缩字符串的方法

Question

我正在尝试问题所在的 Hackerrank 问题

问题陈述

Input: abcaaabbb
output : abca3b3

我的解决方案看起来像

import scala.io.StdIn.readLine

object Solution {

    def main(args: Array[String]) {
        val input = readLine()
        require(input.length > 0, "input string must not be empty.")    
        println(compress(input.tail, input.head, 1, ""))
    }

    def compress(in: String, currentChar: Char, currentCharCount: Int, out: String):String = in.isEmpty match {
        case true => getNewOutput(out, currentChar, currentCharCount)
        case false => in.head match {
            case `currentChar` => compress(in.tail, currentChar, currentCharCount + 1, out)
            case _ => compress(in.tail, in.head, 1, getNewOutput(out, currentChar, currentCharCount))
        }
    }

    def getNewOutput(out:String, currentChar: Char, currentCharCount:Int):String = 
        out + currentChar + (if(currentCharCount == 1) "" else currentCharCount.toString)
}

这很好用，但在两个测试用例上超时。我想知道什么需要花费很多时间？

是匹配吗？还是尾部？

什么是更好的写法？

附言我正在学习 Scala 所以现在请耐心等待我的语法和知识

Answer 1

由于问题被标记为函数式编程/递归，因此预计可以通过尾递归解决。在这种序列遍历中，tailrec 的常用方法是创建额外的累加器参数，该参数在最后处理:

def compress(str: Seq[Char], acc: List[(Char, Int)]): String = str match {
    case first +: rest => compress(rest, acc match {
      case (`first`, n) :: tail => (first, n + 1) :: tail
      case _ => (first, 1) :: acc
    })
    case _ => acc.reverse.view.map {
      case (c, 1) => c.toString
      case (c, n) => s"$c$n"
    }.mkString
  }

尽管像这样的尾递归函数由于可组合性差而很少被认为是好的风格 FP。通常更好的解决方案使用折叠而不是 tailrec:

def compress(str: Seq[Char]): String =
  str.foldLeft(List.empty[(Char, Int)]) { (acc, char) =>
    acc match {
      case (`char`, n) :: tail => (char, n + 1) :: tail
      case _ => (char, 1) :: acc
    }
  }.reverse.view.map {
    case (c, 1) => c.toString
    case (c, n) => s"$c$n"
  }.mkString

我确实费心验证了这两个解决方案在相应的 Hackerrank 问题上都被接受代码

object Solution {
  def compress(...
  def main(args: Array[String]) {
    println(compress(io.StdIn.readLine()))
  }
}

第二个 foldLeft 实现稍微快一些。

您的代码中最麻烦的是 String 连接。由于问题是在某些地方等待 100K 字符的字符串结果，您的

out + currentChar + ... 

多次将小部分附加到很长的前缀。由于 scala 中的 String 是普通的旧 java.lang.String，不像 Vector 那样可以在小的连接中有效地重用大的部分，它打败了你下降到 TL。