使用尾递归计算字符串中字符的出现次数 [英] Counting occurences of characters in a String using tail recursion

问题描述

我不知道如何在 Scala 中使用尾递归计算字符串中字符的出现次数.

I have no clue how to count the occurrences of characters in a string using tail recursion in scala.

我需要用输入运行一个程序

I need to run a program with input

times(explanation)

输出为:

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

到目前为止我尝试运行 RLE，但尾递归的主题对我来说是新的，所以这样做的一些步骤/算法将是完美的

I tried running RLE so far but the topic of tail recursion is new to me, so some steps/algorithm for doing so would be perfect

推荐答案

可能的解决方案:

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

A String is a list of characters. Group them by identity which is (x => x), then count them. Normally groupBy returns a Map which can by transformed to a list of tuples by 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())

}

这篇关于使用尾递归计算字符串中字符的出现次数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！