scala - 字谜递归Scala

Question

这是我试图为其编写代码的问题。

---

考虑一个递归算法，它将两个字符串 s1 和 s2 作为输入，并检查这些字符串是否是彼此的字谜，因此如果所有字母前者包含在后者中出现的次数相同，反之亦然(即s2是s1的排列)。

例子:

如果 s1 = ”elevenplustwo” 和 s2 = “twelveplusone” 输出为真

如果 s1 = ”amina” 和 s2 = “minia” 输出为假

提示: 考虑 s1 的第一个字符 c = s1(0) 和 s1 的其余部分 r =s1.substring(1, s1.size)。对于 c 和 r，s2 必须(递归地)满足什么条件？

---

这是我为解决这个问题而编写的一段代码。问题是当字符串中没有重复字符时，代码可以完美运行。例如，它适用于 amin 和 mina。但是，当有重复时，例如 amina 和 maina，则无法正常工作。

我该如何解决这个问题？

import scala.collection.mutable.ArrayBuffer

object Q32019 extends App {
def anagram(s1:String, s2:String, indexAr:ArrayBuffer[Int]):ArrayBuffer[Int]={

  if(s1==""){
    return indexAr
  }
  else {
  val c=s1(0)
  val s=s1.substring(1,s1.length)
    val ss=s2
    var count=0
   for (i<-0 to s2.length-1) {
    if(s2(i)==c && !indexAr.contains(s2.indexOf(c))) {
      indexAr+=i
      }
    }

    anagram(s,s2,indexAr)
  }
indexAr
}
  var a="amin"
  var b="mina"
  var c=ArrayBuffer[Int]()
  var d=anagram(a,b,c)
  println(d)
  var check=true
  var i=0
  while (i<a.length && check){
    if (d.contains(i) && a.length==b.length) check=true
    else check=false
    i+=1
  }
  if (check) println("yes they are anagram")
  else println("no, they are not anagram")
}

Answer 1

最简单的方法可能是对两个字符串进行排序并进行比较:

def areAnagram(str1: String, str2: String): Boolean =
  str1.sorted == str2.sorted

println(areAnagram("amina", "anima")) // true
println(areAnagram("abc", "bcc"))     // false

---

另一种更“自然”。如果两个字符串每个字符的计数相同，则它们是字谜。
所以你制作两个 Map[Char, Int] 并比较它们:

import scala.collection.mutable

def areAnagram(str1: String, str2: String): Boolean = {
  val map1 = mutable.Map.empty[Char, Int].withDefaultValue(0)
  val map2 = mutable.Map.empty[Char, Int].withDefaultValue(0)
  for (c <- str1) map1(c) += 1
  for (c <- str2) map2(c) += 1
  map1 == map2
}

如果您知道字符只是 ASCII 字符，则可能还有另一个版本的第二个解决方案，其中包含 Arrays。
或者其他一些聪明的算法，IDK。

---

编辑:一种递归解决方案可能是从 str2 中删除 str1 的第一个字符。两个字符串的其余部分也必须是字谜。
例如。对于 ("amina", "niama") 首先你从两者中抛出一个 a，然后你得到 ("mina", "nima")。根据定义，这两个字符串也必须是字谜。

def areAnagram(str1: String, str2: String): Boolean = {

  if (str1.length != str2.length) false
  else if (str1.isEmpty) true // end recursion
  else {
    val (c, r1) = str1.splitAt(1)
    val r2 = str2.replaceFirst(c, "") // remove c
    areAnagram(r1, r2)
  }
}