Анаграмма рекурсия Scala - PullRequest
Новая
       13

Анаграмма рекурсия Scala

2 голосов
/ 19 января 2020

Это вопрос, для которого я пытался написать код.

Рассмотрим рекурсивный алгоритм, который принимает две строки s1 и s2 в качестве входных данных и проверяет, являются ли эти строки анаграммой друг друга, следовательно, если все буквы, содержащиеся в первом, появляются в последнем одинаковое количество раз, и наоборот (то есть s2 является перестановкой s1 ).

Пример:

, если s1 = «elevenplustwo» и s2 = «twelveplusone», выход true

, если s1 = «амина» и s2 = «миния», вывод ложен

Подсказка: рассмотреть первый символ c = s1 (0) для s1 и остальные r = s1 подстрока (1, s1.size) для s1. Каким условиям s2 должен (рекурсивно) удовлетворять в отношении c и r?

И это фрагмент кода, который я написал для решения этой проблемы. Проблема в том, что код отлично работает, когда в строках нет повторения символов. Например, он отлично работает для amin и mina . Тем не менее, когда есть повторение, например, Амина и Маина , то это не работает должным образом.

Как я могу решить эту проблему? 

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

Ответы [ 3 ]

4 голосов
/ 20 января 2020

Самый простой способ - это отсортировать обе строки и просто сравнить их: 

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.
Или какой-то другой умный алгоритм, IDK.

РЕДАКТИРОВАТЬ : Одно рекурсивное решение может удалить первый символ str1 из str2 . Остатки обеих строк также должны быть анаграммами.
Например, для ("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)
  }
}
2 голосов
/ 20 января 2020

Мое предложение: не переусердствуйте. 

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)
2 голосов
/ 20 января 2020

Когда вы вычисляете анаграммы, вы можете воспользоваться свойством операции XOR , которая гласит, что если вы xor двух одинаковых чисел, вы получите 0.

Поскольку символы в строках по существу, просто числа, вы можете запустить xor для всех символов обеих строк, и если результат равен 0, то эти строки являются анаграммами.

Вы можете перебрать обе строки, используя l oop, но если вы хотите использовать Рекурсия, я бы посоветовал вам преобразовать вашу строку в списки символов.

Списки позволяют эффективно разделять первый элемент (заголовок списка) и остальные (хвост списка). Таким образом, решение будет go следующим образом:

  1. Разбить список по заголовкам и хвостам для обоих списков символов.
  2. Выполнить xor над символами, извлеченными из заголовков списков и предыдущего результата.
  3. Передача хвостов списка и результата хоринга следующему рекурсивному вызову.

Когда мы добираемся до конца списков, мы просто возвращаем true - это регистр xoring равен 0 .

Последняя оптимизация, которую мы можем сделать - это короткое замыкание с 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
...