Проверка, являются ли две строки анаграммами — C++, Python, JavaScript

Задача

Даны две строки s1 и s2. Нужно проверить, являются ли они анаграммами друг друга — то есть можно ли получить одну строку, переставив буквы другой.

Примеры

• Пример 1: s1 = “creative”, s2 = “reactive” — это анаграммы.
• Пример 2: s1 = “Peter Piper picked a peck of pickled peppers”, s2 = “A peck of pickled peppers Peter Piper picked” — не анаграммы, если учитывать пробелы и регистр.

Общий алгоритм (коротко)

1. Нормализуйте вход: решите, учитывать ли регистр, пробелы и пунктуацию. Рекомендуется привести к одному регистру и удалить ненужные символы.
2. Если длины после нормализации не совпадают — возвратите false.
3. Либо отсортируйте обе строки и сравните, либо подсчитайте частоту символов и сравните словари.
4. Если совпадает — это анаграмма.

Важное: сортировка даёт сложность O(n log n); подсчёт частот — O(n) по времени и O(k) по памяти, где k — размер алфавита.

C++: проверка анаграмм (пример)

Ниже — корректная и компактная реализация на C++, использующая сортировку строк.

#include 
using namespace std;

bool checkAnagrams(string s1, string s2) {
    if (s1.length() != s2.length()) return false;
    sort(s1.begin(), s1.end());
    sort(s2.begin(), s2.end());
    return s1 == s2;
}

int main() {
    string s1 = "listen";
    string s2 = "silent";
    cout << "String 1: " << s1 << endl;
    cout << "String 2: " << s2 << endl;
    if (checkAnagrams(s1, s2))
        cout << "Yes, the two strings are anagrams of each other" << endl;
    else
        cout << "No, the two strings are not anagrams of each other" << endl;

    // Дополнительно: примеры, включая случаи с пробелами
    string s3 = "Welcome to MUO";
    string s4 = "MUO to Welcome";
    cout << "String 3: " << s3 << endl;
    cout << "String 4: " << s4 << endl;
    if (checkAnagrams(s3, s4))
        cout << "Yes, the two strings are anagrams of each other" << endl;
    else
        cout << "No, the two strings are not anagrams of each other" << endl;

    return 0;
}

Короткое пояснение: код выше считает строки строго — пробелы и регистр учитываются. Для гибкости нормализуйте вход до вызова checkAnagrams.

Python: проверка анаграмм (пример)

Пример на Python, использующий сортировку. Исправленное возвращаемое значение и аккуратная обработка.

def check_anagrams(s1, s2):
    if len(s1) != len(s2):
        return False
    return sorted(s1) == sorted(s2)

s1 = "listen"
s2 = "silent"
print("String 1:", s1)
print("String 2:", s2)
print("Yes, the two strings are anagrams of each other" if check_anagrams(s1, s2) else "No, the two strings are not anagrams of each other")

# Пример с пробелами
s3 = "Welcome to MUO"
s4 = "MUO to Welcome"
print("Yes" if check_anagrams(s3, s4) else "No")

Если нужна линейная сложность, вместо сортировки используйте collections.Counter или словарь частот.

JavaScript: проверка анаграмм (пример)

Ниже — исправленный пример на JavaScript. Функция принимает строки, разбивает их на массив символов, сортирует и сравнивает.

function checkAnagrams(s1, s2) {
  if (s1.length !== s2.length) return false;
  const a1 = s1.split("").sort().join("");
  const a2 = s2.split("").sort().join("");
  return a1 === a2;
}

const s1 = "listen";
const s2 = "silent";
console.log("String 1:", s1);
console.log("String 2:", s2);
console.log(checkAnagrams(s1, s2) ? "Yes, the two strings are anagrams of each other" : "No, the two strings are not anagrams of each other");

Важно: сортировка в JavaScript также имеет сложность O(n log n). Для больших строк предпочтительнее подсчёт частот.

Альтернативный подход: подсчёт частот (O(n))

• Пройдите по первой строке и увеличьте счётчик для каждого символа.
• Пройдите по второй строке и уменьшите счётчик для каждого символа.
• Если в конце все значения счётчиков равны нулю, строки — анаграммы.

Этот метод лучше по времени для длинных строк и ограниченного алфавита.

Когда алгоритм даёт неверный результат (частые ошибки)

• Не нормализованы строки: регистр и пробелы различаются.
• Пунктуация и диакритика влияют на сравнение.
• Для Unicode-символов требуется нормализация (NFC/NFD) перед сравнением.

Важно: всегда заранее решить, какие символы считать значимыми.

Быстрые эвристики и полезные правила

• Если строки разных длин после удаления пробелов/знаков — не анаграммы.
• Для латинского алфавита используйте массив длиной 26 для частот; для произвольного Unicode — словарь.
• Для частых проверок на одной паре строк сортировка проще; для массовых проверок — подсчёт частот эффективнее.

Факты о производительности

• Сортировка: O(n log n) по времени, O(1)–O(n) по памяти (в зависимости от алгоритма сортировки).
• Подсчёт частот: O(n) по времени, O(k) по памяти (k — размер алфавита).

Ролевая чек-лист для команды

• Разработчик: нормализовать вход, выбрать метод (сортировка/частоты), покрыть тестами.
• Ревьюер: проверить обработку Unicode и регистров, убедиться в тестах на граничные случаи.
• QA: добавить тесты со знаками, разным регистром, повторяющимися символами и пустой строкой.

Критерии приёмки

• Алгоритм корректно определяет анаграммы для ASCII и для заданной политики нормализации.
• Тесты покрывают: пустые строки, строки разной длины, строки с пробелами и пунктуацией, Unicode.
• Время выполнения соответствует выбранной стратегии (подсчёт частот для больших объёмов).

Тестовые случаи

• (“”, “”) => true
• (“a”, “a”) => true
• (“ab”, “ba”) => true
• (“a b”, “ab “) с нормализацией пробелов => true или false в зависимости от политики
• (“listen”, “silent”) => true
• Очень длинные строки с повторяющимися символами — проверить производительность

Краткое резюме

Анаграммы удобно проверять двумя способами: сортировкой символов (просто и понятно) и подсчётом частот (эффективно для больших данных). Всегда нормализуйте вход, решите заранее, учитывать ли пробелы и регистр, и добавьте тесты на Unicode и граничные случаи.

Важно: выбирайте метод в зависимости от типа и размера данных. Если вы часто проверяете тысячи пар коротких строк — сортировка подойдёт. Если строки длинные или данных много — используйте подсчёт частот.