Проверка анаграмм в C++, Python и JS

мужчина за ноутбуком с логотипами 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” — нет, не анаграммы (регистр и пробелы меняют совпадение при простом сравнении).

Важно: прежде чем сравнивать следует решить, учитывать ли пробелы, пунктуацию и регистр. В большинстве практических задач пробелы и регистр игнорируют, а иногда требуется точное совпадение.

Процесс проверки анаграмм (основной подход)

Нормализуйте строки по правилам задачи: например, удалить пробелы, убрать пунктуацию, привести к нижнему регистру, сделать Unicode-нормализацию (NFC/NFD) при необходимости.
Сравните длины нормализованных строк. Если длины разные — вернуть false.
Отсортируйте символы каждой строки.
Сравните отсортированные строки. Если они совпадают — это анаграммы, иначе нет.

Этот подход прост и надёжен, но требует O(n log n) времени из-за сортировки.

Когда метод на основе сортировки не подходит

Important: сортировка удобна, но бывает неэффективна для очень длинных строк или когда важна скорость в реальном времени.

Типичные проблемы и ошибки:

Наличие пробелов и пунктуации: строка с пробелами не станет анаграммой строки без пробелов без предварительной очистки.
Регистр: “Listen” и “silent” — без приведения к одному регистру не считаются анаграммами.
Unicode: комбинированные символы (например, é) могут иметь разные представления; нужно нормализовать.
Алфавит нефиксирован: если допустимы символы вне ASCII, массив счётчиков должен покрывать нужный набор или использовать словарь.

Альтернативные подходы

Счётчик символов (рекомендуется для производительности): пройти по первой строке и увеличить счётчик для каждого символа, затем пройти по второй строке и уменьшить. Если в конце все счётчики равны нулю — строки анаграммы. Это O(n) по времени и O(k) по памяти, где k — размер алфавита/число уникальных символов.
Математические хэш-методы (редко применяются в чистом виде): вычислять хэш-значение на основе частот; нужно быть осторожным с коллизиями.
Битовые/числовые трюки применимы только для очень ограниченных алфавитов.

Ниже приведены исходные реализации на C++, Python и JavaScript (с сохранением оригинального кода). После блоков кода приведены рекомендации по улучшению и примеры тестов.

C++ Программа для проверки анаграмм

Ниже исходный C++ код:

#include   
using namespace std;  
  
bool checkAnagrams(string s1, string s2)  
{  
 int size1 = s1.length();  
 int size2 = s2.length();  
  
 // If the length of both strings are not the same,  
 // it means they can't be anagrams of each other.  
 // Thus, return false.  
 if (size1 != size2)  
 {  
 return false;  
 }  
  
 sort(s1.begin(), s1.end());  
 sort(s2.begin(), s2.end());  
  
 for (int i = 0; i < size1; i++)  
 {  
 if (s1[i] != s2[i])  
 {  
 return false;  
 }  
  
}  
  
return true;  
}  
  
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;  
 }  
  
 string s5 = "Peter Piper picked a peck of pickled peppers";  
 string s6 = "A peck of pickled peppers Peter Piper picked";  
 cout << "String 5: " << s5 << endl;  
 cout << "String 6: " << s6 << endl;  
 if(checkAnagrams(s5, s6))  
 {  
 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 s7 = "She sells seashells by the seashore";  
 string s8 = "seashells by the seashore";  
 cout << "String 7: " << s7 << endl;  
 cout << "String 8: " << s8 << endl;  
 if(checkAnagrams(s7, s8))  
 {  
 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 s9 = "creative";  
 string s10 = "reactive";  
 cout << "String 9: " << s9 << endl;  
 cout << "String 10: " << s10 << endl;  
 if(checkAnagrams(s9, s10))  
 {  
 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;  
}

Вывод программы (оригинальный):

String 1: listen  
String 2: silent  
Yes, the two strings are anagrams of each other  
String 3: Welcome to MUO  
String 4: MUO to Welcome  
Yes, the two strings are anagrams of each other  
String 5: Peter Piper picked a peck of pickled peppers  
String 6: A peck of pickled peppers Peter Piper picked  
No, the two strings are not anagrams of each other  
String 7: She sells seashells by the seashore  
String 8: seashells by the seashore  
No, the two strings are not anagrams of each other  
String 9: creative  
String 10: reactive  
Yes, the two strings are anagrams of each other

Рекомендации по улучшению C++-версии:

Нормализуйте строки: удаляйте пробелы, приводите к одному регистру, при необходимости удаляйте пунктуацию.
Для лучшей производительности используйте подсчёт частот: std::unordered_map или в случае ASCII — std::array.
При работе с Unicode используйте std::u32string/codecvt и нормализацию.

Пример улучшённой идеи на C++ (описание): пройти по символам первой строки, увеличить счётчик; по второй — уменьшить; затем проверить, что все счётчики ноль.

Python Программа для проверки анаграмм

Ниже исходный Python код:

def checkAnagrams(s1, s2):  
    size1 = len(s1)  
    size2 = len(s2)  
  
    # If the length of both strings are not the same,  
    # it means they can't be anagrams of each other.  
    # Thus, return false.  
    if size1 != size2:  
        return 0  
  
    s1 = sorted(s1)  
    s2 = sorted(s2)  
  
    for i in range(0, size1):  
        if s1[i] != s2[i]:  
            return False  
  
    return True  
  
  
s1 = "listen"  
s2 = "silent"  
print("String 1: ", s1)  
print("String 2: ", s2)  
if(checkAnagrams(s1, s2)):  
    print("Yes, the two strings are anagrams of each other")  
else:  
    print("No, the two strings are not anagrams of each other")  
  
s3 = "Welcome to MUO"  
s4 = "MUO to Welcome"  
print("String 3: ", s3)  
print("String 4: ", s4)  
if(checkAnagrams(s3, s4)):  
    print("Yes, the two strings are anagrams of each other")  
else:  
    print("No, the two strings are not anagrams of each other")  
  
s5 = "Peter Piper picked a peck of pickled peppers"  
s6 = "A peck of pickled peppers Peter Piper picked"  
print("String 5: ", s5)  
print("String 6: ", s6)  
if(checkAnagrams(s5, s6)):  
    print("Yes, the two strings are anagrams of each other")  
else:  
    print("No, the two strings are not anagrams of each other")  
  
s7 = "She sells seashells by the seashore"  
s8 = "seashells by the seashore"  
print("String 7: ", s7)  
print("String 8: ", s8)  
if(checkAnagrams(s7, s8)):  
    print("Yes, the two strings are anagrams of each other")  
else:  
    print("No, the two strings are not anagrams of each other")  
  
s9 = "creative"  
s10 = "reactive"  
print("String 9: ", s9)  
print("String 10: ", s10)  
if(checkAnagrams(s9, s10)):  
    print("Yes, the two strings are anagrams of each other")  
else:  
    print("No, the two strings are not anagrams of each other")

Вывод программы (оригинальный):

String 1: listen  
String 2: silent  
Yes, the two strings are anagrams of each other  
String 3: Welcome to MUO  
String 4: MUO to Welcome  
Yes, the two strings are anagrams of each other  
String 5: Peter Piper picked a peck of pickled peppers  
String 6: A peck of pickled peppers Peter Piper picked  
No, the two strings are not anagrams of each other  
String 7: She sells seashells by the seashore  
String 8: seashells by the seashore  
No, the two strings are not anagrams of each other  
String 9: creative  
String 10: reactive  
Yes, the two strings are anagrams of each other

Рекомендации по улучшению Python-версии:

Вместо сортировки используйте collections.Counter: return Counter(s1) == Counter(s2).
Нормализуйте строки перед сравнением: s = ‘’.join(ch.lower() for ch in s if ch.isalnum()).
Для очень больших строк избегайте аллокаций при сортировке.

JavaScript Проверка анаграмм

Ниже исходный JavaScript код:

function checkAnagrams(s1, s2) {  
 let size1 = s1.length;  
 let size2 = s2.length;  
  
// If the length of both strings are not the same,  
 // it means they can't be anagrams of each other.  
 // Thus, return false.  
 if (size1 != size2)  
 {  
 return false;  
 }  
  
 s1.sort();  
 s2.sort();  
  
 for (let i = 0; i < size1; i++)  
 {  
 if (s1[i] != s2[i])  
 {  
 return false;  
 }  
  
}  
  
return true;  
}  
  
  
var s1 = "listen";  
var s2 = "silent";  
document.write("String 1: " + s1 + "  \n");  
document.write("String 2: " + s2 + "  \n");  
if(checkAnagrams(s1.split(""), s2.split(""))) {  
 document.write("Yes, the two strings are anagrams of each other" + "  \n");  
} else {  
 document.write("No, the two strings are not anagrams of each other" + "  \n");  
}  
  
var s3 = "Welcome to MUO";  
var s4 = "MUO to Welcome";  
document.write("String 3: " + s3 + "  \n");  
document.write("String 4: " + s4 + "  \n");  
if(checkAnagrams(s3.split(""), s4.split(""))) {  
 document.write("Yes, the two strings are anagrams of each other" + "  \n");  
} else {  
 document.write("No, the two strings are not anagrams of each other" + "  \n");  
}  
  
var s5 = "Peter Piper picked a peck of pickled peppers";  
var s6 = "A peck of pickled peppers Peter Piper picked";  
document.write("String 5: " + s5 + "  \n");  
document.write("String 6: " + s6 + "  \n");  
if(checkAnagrams(s5.split(""), s6.split(""))) {  
 document.write("Yes, the two strings are anagrams of each other" + "  \n");  
} else {  
 document.write("No, the two strings are not anagrams of each other" + "  \n");  
}  
  
var s7 = "She sells seashells by the seashore";  
var s8 = "seashells by the seashore";  
document.write("String 7: " + s7 + "  \n");  
document.write("String 8: " + s8 + "  \n");  
if(checkAnagrams(s7.split(""), s8.split(""))) {  
 document.write("Yes, the two strings are anagrams of each other" + "  \n");  
} else {  
 document.write("No, the two strings are not anagrams of each other" + "  \n");  
}  
  
var s9 = "creative";  
var s10 = "reactive";  
document.write("String 9: " + s9 + "  \n");  
document.write("String 10: " + s10 + "  \n");  
if(checkAnagrams(s9.split(""), s10.split(""))) {  
 document.write("Yes, the two strings are anagrams of each other" + "  \n");  
} else {  
 document.write("No, the two strings are not anagrams of each other" + "  \n");  
}

Вывод (оригинальный):

String 1: listen  
String 2: silent  
Yes, the two strings are anagrams of each other  
String 3: Welcome to MUO  
String 4: MUO to Welcome  
Yes, the two strings are anagrams of each other  
String 5: Peter Piper picked a peck of pickled peppers  
String 6: A peck of pickled peppers Peter Piper picked  
No, the two strings are not anagrams of each other  
String 7: She sells seashells by the seashore  
String 8: seashells by the seashore  
No, the two strings are not anagrams of each other  
String 9: creative  
String 10: reactive  
Yes, the two strings are anagrams of each other

Замечания по JavaScript-версии:

В исходном коде метод sort вызывается на строковых массивах, это допустимо только если вы передаёте массивы символов. Лучше явно делать s.split(“”).sort().join(“”) или использовать подсчёт частот.
Для производительности используйте объект-словарь для подсчёта частот.

Ментальные модели и эвристики

Если задача на интервью: начинайте с требований — учитывать ли пробелы и регистр. Это показывает внимательность.
Если строка длинная и система чувствительна к времени, выбирайте подсчёт частот вместо сортировки.
Для ограниченного алфавита (например, только строчные латинские буквы) можно использовать массив фиксированной длины (26).

Критерии приёмки (тест-кейсы)

Простейший положительный: “listen” vs “silent” → true.
Учитывая регистр: “Listen” vs “silent” → в зависимости от требований: если регистр игнорируется — true.
С пробелами: “a b c” vs “cab” → при удалении пробелов true.
Разная длина: “abc” vs “ab” → false.
Unicode: разные нормализованные формы одного символа — требуется нормализация.
Пустые строки: “” vs “” → true.

Фактбокс: сложность и ресурсы

Метод сортировки: время O(n log n), память O(n) (для сортировки обычно требуется доп. память).
Метод подсчёта частот: время O(n), память O(k) — k = размер алфавита/число уникальных символов.
Практическая рекомендация: если n > 10^5 и требования по скорости жёсткие — используйте подсчёт частот.

Шаблон проверки в псевдокоде (быстрый алгоритм)

Нормализовать s1 и s2 по правилам (регистры, пробелы, нормализация Unicode).
Если длины отличаются — вернуть false.
Создать пустой словарь counts.
Для каждого символа c в s1: counts[c]++.
Для каждого символа c в s2: counts[c]–. Если counts[c] < 0 → вернуть false.
Вернуть true.

Роли: чек-лист для интервьюера и кандидата

Для кандидата:

Уточнить требования (учёт регистра, пробелов, пунктуации, Unicode).
Пояснить сложность предложенного решения.
При возможности предложить оптимизацию (счётчики).

Для интервьюера:

Оценить, как кандидат нормализует вход.
Спросить про сложность и альтернативы.
Проверить на крайних случаях (Unicode, длинные строки).

Резюме

Сравнение по сортировке — простая и понятная реализация, но для производительности лучше использовать подсчёт частот символов. Обязательно уточняйте требования к нормализации входных данных. Простые тесты (разная длина, пустые строки, пробелы, регистр) покрывают большинство ошибок.

Use the Right Resources to Learn to Code: если вы хотите закрепить навыки, практикуйтесь в задачах на строковые операции и используйте специализированные приложения и онлайн-платформы.