Проверка анаграммы Скала частности, осуществление на основе


Вот в HashMap на основе реализации функции проверки, являются ли две строки анаграммами:

Пример:

isAnagram("SAVE", "VASE") // returns true
isAnagram("SAV",  "VASE") // returns false
isAnagram("SAVE", "VAS")  // returns false
isAnagram("SAVE", "VAEE") // returns false

Моя реализация:

def isAnagram(value1: String, value2: String): Boolean = {
  value1.length == value2.length && {
    val index = new mutable.HashMap[Char, Int]()

    def addToIndex(c: Char) = index(c) = index.getOrElse(c, 0) + 1

    value1.foreach(c => addToIndex(c))

    def decrementAndCheckInIndex(c: Char): Boolean = index.get(c) match {
      case None => false
      case Some(count) => index(c) = count - 1; true
    }

    value2.forall(decrementAndCheckInIndex) && index.forall { case (key, value) => value == 0 }
  }
}

Не могли бы вы, пожалуйста, предоставить отзыв на этот код. Я заинтересован в мутабельном использовать структуры данных, это нормально? И вообще, что я могу сделать лучше?



Комментарии
1 ответ

Мне кажется, что groupBy() будет делать что-то очень похожее на ваш addToIndex(). В результате immutable.Map[Char,String] вместо mutable.HashMap[Char, Int]вопрос такой: что лучше/проще для целей сравнения.

Получается, что простой == оценки достаточно глубоко, чтобы справиться с этим.

def isAnagram(value1: String, value2: String): Boolean =
value1.groupBy(identity) == value2.groupBy(identity)

Еще один, довольно очевидный, тест анаграмма-это просто:

value1.sorted == value2.sorted

Я думаю, для длинных строк, группировка/индексации может быть более эффективной, чем сортировка с каждой строки проходится только один раз. С другой стороны, сравнение на равенство может быть более сложным для MapС чем будет StringС.

2
ответ дан 6 марта 2018 в 08:03 Источник Поделиться