时间戳

首页 > 解决方案 > 从scala中的给定字符串返回旋转等价对列表

scala - 从scala中的给定字符串返回旋转等价对列表

问题描述

输入字符串

["ac","bd","ce","aaa","xyz","bbb","abc","kt","zb"]

我想要以下输出：

[列表（“ac”，“bd”，“ce”，“zb”），列表（“aaa”，“bbb”），列表（“abc”，“xyz”），列表（“kt”）]

这里的逻辑是我需要将类似的元素分组到列表中。

第一个列表中的模式是，我跳过了一个字母。

第二个列表中的模式是，我有一个字母重复三次。

第三个列表中的模式是，我有 3 个连续的字母。

在对所有这些进行分组之后，我有一个元素不属于上述任何模式，因此将其添加到单独的列表中。

我不确定scala中的算法/解决方案。任何帮助表示赞赏。TIA。

标签： scala

解决方案

构造字符串的旋转等价表示的方法。

  def normalizedRepresentation(str: String) = {
    str.map(char => (char - str.charAt(0) + 'a').asInstanceOf[Char])
  }

  def rotationalEquivalenceRepresentation(str: String) = {
    val normalizedStr = normalizedRepresentation(str)
    normalizedStr.map(char => if (char < 'a') (char + 26).asInstanceOf[Char] else char.asInstanceOf[Char])
  }

然后

scala>   val input = List("ac","bd","ce", "aaa","xyz","bbb","abc","kt","zb")
input: List[String] = List(ac, bd, ce, aaa, xyz, bbb, abc, kt, zb)

scala>   input.map(str => normalizedRepresentation(str))
res0: List[String] = List(ac, ac, ac, aaa, abc, aaa, abc, aj, aI)

scala>   input.map(str => rotationalEquivalenceRepresentation(str))
res1: List[String] = List(ac, ac, ac, aaa, abc, aaa, abc, aj, ac)

scala> 

scala>   input.groupBy(str => rotationalEquivalenceRepresentation(str))
res2: scala.collection.immutable.Map[String,List[String]] = Map(abc -> List(xyz, abc), aaa -> List(aaa, bbb), ac -> List(ac, bd, ce, zb), aj -> List(kt))

scala>   input.groupBy(str => rotationalEquivalenceRepresentation(str)).values.toList
res3: List[List[String]] = List(List(xyz, abc), List(aaa, bbb), List(ac, bd, ce, zb), List(kt))

推荐阅读