Проверьте, являются ли две строки анаграммами, используя переполнение стека

Алгоритм также не работает, когда его просят найти aa а также aa анаграммы Попробуйте отследить шаги алгоритма мысленно или в отладчике, чтобы выяснить, почему; вы узнаете больше таким образом.

Кстати … Обычный метод поиска анаграмм — это подсчет того, сколько раз каждая буква встречается в строках. Количество должно быть равным для каждой буквы. Этот подход имеет O (n) сложность времени в отличие от O (n²).

bool areAnagram(char *str1, char *str2)
{
// Create two count arrays and initialize all values as 0
int count1[NO_OF_CHARS] = {0};
int count2[NO_OF_CHARS] = {0};
int i;

// For each character in input strings, increment count in
// the corresponding count array
for (i = 0; str1[i] && str2[i];  i++)
{
count1[str1[i]]++;
count2[str2[i]]++;
}

// If both strings are of different length. Removing this condition
// will make the program fail for strings like "aaca" and "aca"if (str1[i] || str2[i])
return false;

// Compare count arrays
for (i = 0; i < NO_OF_CHARS; i++)
if (count1[i] != count2[i])
return false;

return true;
}

Я вижу 2 основных подхода ниже:

1. Сортируй потом сравни
2. Подсчитайте вхождения каждой буквы

Интересно видеть, что хорошее решение Сураджа получило одно очко (на мой взгляд, на момент написания), а какое-то одно — 22. Объяснение заключается в том, что производительность не была в голове у людей — и это хорошо для коротких строк.

Реализация сортировки имеет длину всего 3 строки, но счетчик превосходит его для длинных строк. Это намного быстрее (O (N) против O (NlogN)).
Получил следующие результаты с длиной строки 500 МБ.

1. Сортировать — 162,8 с
2. подсчитывать — 2,864 секунды
3. Многопоточный граф — 3.321 сек

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

Я был бы рад увидеть какую-то идею, которая ускорила бы решение подсчета (подумайте, кто-то хорошо разбирается в проблемах с задержкой памяти, кеширует).

#include<stdio.h>
#include<string.h>
int is_anagram(char* str1, char* str2){
if(strlen(str1)==strspn(str1,str2) && strlen(str1)==strspn(str2,str1) &&
strlen(str1)==strlen(str2))
return 1;
return 0;
}
int main(){
char* str1 = "stream";
char* str2 = "master";
if(is_anagram(str1,str2))
printf("%s and %s  are anagram to each other",str1,str2);
else
printf("%s and %s  are not anagram to each other",str1,str2);
return 0;
}

#include<iostream>
#include<unordered_map>
using namespace std;

int checkAnagram (string &str1, string &str2)
{
unordered_map<char,int> count1, count2;
unordered_map<char,int>::iterator it1, it2;
int isAnagram = 0;

if (str1.size() != str2.size()) {
return -1;
}

for (unsigned int i = 0; i < str1.size(); i++) {
if (count1.find(str1[i]) != count1.end()){
count1[str1[i]]++;
} else {
count1.insert(pair<char,int>(str1[i], 1));
}
}

for (unsigned int i = 0; i < str2.size(); i++) {
if (count2.find(str2[i]) != count2.end()) {
count2[str2[i]]++;
} else {
count2.insert(pair<char,int>(str2[i], 1));
}
}

for (unordered_map<char, int>::iterator itUm1 = count1.begin(); itUm1 != count1.end(); itUm1++) {
unordered_map<char, int>::iterator itUm2 = count2.find(itUm1->first);
if (itUm2 != count2.end()) {
if (itUm1->second != itUm2->second){
isAnagram = -1;
break;
}
}
}

return isAnagram;
}

int main(void)
{
string str1("WillIamShakespeare");
string str2("IamaWeakishSpeller");

cout << "checkAnagram() for " << str1 << "," << str2 << " : " << checkAnagram(str1, str2) << endl;

return 0;
}

Забавно, что иногда самые лучшие вопросы самые простые.

Проблема здесь состоит в том, как определить, являются ли два слова анаграммами — слово, по сути, является несортированным мультимножеством символов.

Мы знаем, что мы должны отсортировать, но в идеале мы бы хотели избежать сложности времени.

Оказывается, что во многих случаях мы можем исключить много слов, которые отличаются в линейное время запустив их оба и запустив значения символов в накопитель. Общий XOR всех символов в обеих строках должен быть равен нулю, если обе строки являются анаграммами, независимо от порядка. Это потому, что все, что связано с самим собой, становится нулем.

Конечно, обратное неверно. То, что аккумулятор равен нулю, не означает, что у нас есть совпадение анаграмм.

Используя эту информацию, мы можем устранить многие неанаграммы без сортировки, закорачивая по крайней мере случай без анаграммы.

#include <iostream>
#include <string>
#include <algorithm>

//
// return a sorted copy of a string
//
std::string sorted(std::string in)
{
std::sort(in.begin(), in.end());
return in;
}

//
// check whether xor-ing the values in two ranges results in zero.
// @pre first2 addresses a range that is at least as big as (last1-first1)
//
bool xor_is_zero(std::string::const_iterator first1,
std::string::const_iterator last1,
std::string::const_iterator first2)
{
char x = 0;
while (first1 != last1) {
x ^= *first1++;
x ^= *first2++;
}
return x == 0;
}

//
// deduce whether two strings are the same length
//
bool same_size(const std::string& l, const std::string& r)
{
return l.size() == r.size();
}

//
// deduce whether two words are anagrams of each other
// I have passed by const ref because we may not need a copy
//
bool is_anagram(const std::string& l, const std::string& r)
{
return same_size(l, r)
&& xor_is_zero(l.begin(), l.end(), r.begin())
&& sorted(l) == sorted(r);
}

// test

int main()  {

using namespace std;

auto s1 = "apple"s;
auto s2 = "eppla"s;

cout << is_anagram(s1, s2) << '\n';

s2 = "pppla"s;

cout << is_anagram(s1, s2) << '\n';

return 0;
}

Ожидаемый результат:

1
0

Вот самый простой и быстрый способ проверить наличие анаграмм

bool anagram(string a, string b) {
int a_sum = 0, b_sum = 0, i = 0;
while (a[i] != '\0') {
a_sum += (int)a[i]; // (int) cast not necessary
b_sum += (int)b[i];
i++;
}
return a_sum == b_sum;
}

Просто добавляет значения ASCII и проверяет, равны ли суммы.

Например:
строка a = «nap» и строка b = «pan»
a_sum = 110 + 97 + 112 = 319
b_sum = 112 + 97 + 110 = 319