Анаграммы — это слова или фразы, образованные перестановкой букв другого слова или фразы. В этой статье блога мы рассмотрим различные методы поиска всех анаграмм в строке с помощью Scala. Мы предоставим примеры кода для каждого метода и обсудим их эффективность.

Метод 1: подход грубой силы
Подход грубой силы включает в себя генерацию всех возможных перестановок входной строки и проверку того, является ли каждая перестановка допустимой анаграммой. Хотя этот метод прост, он крайне неэффективен для больших входных строк из-за экспоненциальной временной сложности.

Код Scala:

def findAnagramsBruteForce(str: String): List[String] = {
  str.permutations.filter(_ != str).toList
}

Метод 2: Карта частот символов
Один из эффективных подходов — создать карту частот символов как для входной строки, так и для потенциальных анаграмм. Сравнивая карты, мы можем быстро выявить анаграммы. Временная сложность этого метода равна O(n), где n — длина входной строки.

Код Scala:

import scala.collection.mutable
def findAnagramsCharMap(str: String): List[String] = {
  val charMap = mutable.Map.empty[Char, Int].withDefaultValue(0)
  str.foreach(c => charMap(c) += 1)

  str.permutations.filter(anagram => {
    val anagramMap = mutable.Map.empty[Char, Int].withDefaultValue(0)
    anagram.foreach(c => anagramMap(c) += 1)
    charMap == anagramMap
  }).toList
}

Метод 3. Сортировка
Другой эффективный подход — сортировка символов входной строки и потенциальных анаграмм. Если две строки являются анаграммами, их отсортированные версии будут идентичны. Этот метод имеет временную сложность O(n log n), где n — длина входной строки.

Код Scala:

def findAnagramsSorting(str: String): List[String] = {
  val sortedStr = str.sorted
  str.permutations.filter(anagram => anagram.sorted == sortedStr).toList
}

В этой статье блога мы рассмотрели три различных метода поиска всех анаграмм в строке с помощью Scala. Мы обсудили подход грубой силы, подход карты частоты символов и подход сортировки. Хотя метод грубой силы неэффективен для больших входных данных, подходы с использованием карты частот символов и сортировки обеспечивают эффективные решения. В зависимости от конкретных требований и ограничений вашего приложения вы можете выбрать наиболее подходящий метод.