Anagram Recursion Scala

Question

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

---

考虑一种递归算法，该算法采用两个字符串s1和s2作为输入，并检查这些字符串是否彼此相似，因此前者中包含的所有字母是否都出现在后者中相同的次数，反之亦然（即s2是s1的排列）。

示例：

如果s1 =“十一加二”并且s2 =“十二加一”，则输出为true

如果s1 =“ amina”并且s2 =“ minia”，则输出为假

提示： 考虑s1的第一个字符c = s1（0），其余的r = s1.substring（1，s1.size）。 s2关于c和r必须（递归）满足的条件是什么？

---

这是我为解决此问题而编写的代码。问题是当字符串中没有重复的字符时，代码可以完美地工作。例如，它对于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字符，则可能还有第二个解决方案的另一个版本，它带有Array。或其他一些聪明的算法，IDK。

---

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

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

[计算字谜时，您可以利用XOR

操作的属性，即如果对两个相同的数字进行异或运算，您将得到0。

由于字符串中的字符本质上只是数字，因此您可以对两个字符串的所有字符进行异或运算，如果结果为0，则这些字符串为字谜。

您可以使用循环遍历两个字符串，但是如果您要使用递归，我建议您将字符串转换为字符列表。

列表允许在第一个元素（列表的头部）和其余元素（列表的尾部）之间进行有效拆分。因此解决方案将如下所示：

1. 将两个字符的列表拆分为头部和尾部。
2. 对从列表的开头和先前结果中提取的字符进行异或运算。
3. 将列表尾部和异或结果传递到下一个递归调用。

到达列表末尾时，如果异或的结果为0，则仅返回true

。

我们可以做的最后一个优化是，每当传递不同长度的字符串时，都使用false进行短时间加密（因为无论如何它们永远都不可能是字谜）。

最终解决方案：

def anagram(a: String, b: String): Boolean = {

  //inner function doing recursion, annotation @tailrec makes sure function is tail-recursive
  @tailrec
  def go(a: List[Char], b: List[Char], acc: Int): Boolean = { //using additional parameter acc, allows us to use tail-recursion, which is safe for stack
    (a, b) match {
      case (x :: xs, y :: ys) => //operator :: splits list to head and tail
        go(xs, ys, acc ^ x ^ y) //because we changed string to lists of chars, we can now efficiently access heads (first elements) of lists
      //we get first characters of both lists, then call recursively go passing tails of lists and result of xoring accumulator with both characters
      case _ => acc == 0 //if result of xoring whole strings is 0, then both strings are anagrams
    }
  }

  if (a.length != b.length) { //we already know strings can't be anagrams, because they've got different size
    false
  } else {
    go(a.toList, b.toList, 0)
  }
}

anagram("twelveplusone", "elevenplustwo") //true
anagram("amina", "minia") //false

我的建议：不要想太多。

def anagram(a: String, b: String): Boolean =
  if (a.isEmpty) b.isEmpty
  else b.contains(a(0)) && anagram(a.tail, b diff a(0).toString)

Answer 2

[计算字谜时，您可以利用XOR

Answer 3

我的建议：不要想太多。