使用尾递归计算字符串中字符的出现

Question

我不知道如何使用scala中的尾递归来计算字符串中字符的出现次数。

我需要与输入

times(explanation) 

运行程序并输出结果是：

List((e,1), (x,1), (p,1), (l,1), (a,2), (n,2), (t,1), (i,1), (o,1)) 

我试图运行RLE，但迄今为止尾递归的话题是新的给我，所以一些这样做的步骤/算法将是完美的

Answer 1

可能的解决方案：

A字符串是一个字符列表。 按身份（x => x）对它们进行分组，然后对它们进行计数。 通常groupBy返回一个Map，它可以通过toList转换为元组列表。

代码/不重新发明轮子

def times(s: String) = s.groupBy(identity).mapValues(_.size).toList 
times: (s: String)List[(Char, Int)] 

例

times("explanation") 
res1: List[(Char, Int)] = List((e,1), (x,1), (n,2), (t,1), (a,2), (i,1), (l,1), (p,1), (o,1)) 

代码与尾递归/重塑车轮/请使用未在Coursera Scala的欺骗场

import scala.annotation.tailrec 

def myTimes(s: String) : List[(Char,Int)] = { 

    @tailrec // comiler cheks if really tailrecursive 
    def timesTail(chars: List[Char], res: List[(Char,Int)]) : List[(Char,Int)] = 
    chars match { 
     case Nil => res  // we are done when there are no characters left 
     case char :: rest => { 
      // otherwise 
      val newCharCount = 
      res. 
       find (_._1 == char). //check if we already have seen the character 
       map{ case (c,count) => (c,count + 1) }. // if yes, we raise take the old count and raise it by one 
       getOrElse((char,1)) // otherwise we count one occurrence 
      // here it gets recursive 
      timesTail(
       rest, // remaining Characters 
       newCharCount :: res.filterNot(_._1 == char) // add the new count to list, remove old if present 
     ) 
     } 
    } 
    // initial call with empty lsit to start the helper function 
    timesTail(s.toList,List()) 

} 

Answer 2

高效，这不是。但它是尾递归的，并且输出的顺序与问题中的顺序相同，以防万一。如果这不是一项任务，那么Andreas的groupBy解决方案是更好的解决方案。

def times(s: String) = { 
    def timesRecurse(s: String, result: List[(Char, Int)]): List[(Char, Int)] = { 
     if (s.isEmpty) 
     result 
     else { 
     val c = s.head 
     val i = result.indexWhere(_._1 == c) 
     timesRecurse(s.tail, 
      if (i == -1) 
       (c, 1) :: result 
      else 
      result updated (i, (c, result(i)._2 + 1))) 
     } 

    } 
    timesRecurse(s, List[(Char, Int)]()).reverse 
    } 

    times("explanation") 
    //> res0: List[(Char, Int)] = 
    // List((e,1), (x,1), (p,1), (l,1), (a,2), (n,2), (t, 1), (i,1), (o,1))