变位词递归Scala

Question

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

---

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

例如：

如果s1 = "elevenplustwo"和s2 = "twelveplusone"，则输出为true 如果s1 = "amina"和s2 = "minia"，则输出为false 提示：考虑s1的第一个字符c=s1(0)和r=s1.substring(1,s1.size)的其余部分。关于c和r，s2必须(recursively)满足什么条件？

---

以下是我编写的解决此问题的代码。该代码在字符串中没有重复字符时工作得很好。例如，对于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")
}

- user12743563

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
}

还有另一种可能使用Array的第二种解决方案，如果你知道字符只是ASCII码。
或者使用其他聪明的算法，我不知道。

---

编辑：一个递归解决方案是从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)
  }
}

- insan-e

---

谢谢。当然，排序和比较是最好的解决方案，但问题在于我需要使用问题提供的提示，而使用递归非常重要。 - user12743563

@user12743563 我也添加了一个递归解决方案。 :D - insan-e

Answer 2

当你计算变位词时，可以利用XOR操作的特性，即如果你对两个相同的数字进行异或运算，则得到0。

由于字符串中的字符本质上只是数字，因此您可以在两个字符串的所有字符上运行xor，如果结果为0，则这些字符串是变位词。

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

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

1. 将字符列表分割为列表头和列表尾。
2. 对从列表头中提取的字符和以前的结果执行xor运算。
3. 传递列表尾和xoring结果给下一个递归调用。

当我们到达列表末尾时，如果xoring结果为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

- Krzysztof Atłasik

Answer 3

我的建议是：不要想得太多。

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)

- jwvh