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

Question

输入字符串

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

我想要以下输出:

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

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

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

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

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

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

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

Answer 1

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

  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))