Проверка, являются ли две строки анаграммой

Question

Проверка, являются ли две строки анаграммой

Задаче задаются две строки, проверьте, являются ли две заданные строки анаграмма друг от друга или нет. Анаграмма строки — это другая строка, содержащая те же символы, только порядок символов может быть другим. Например, «действовать» и «так» являются анаграммы друг друга.

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

Выход:
Выведите «YES» без кавычек, если две строки анаграммы, иначе выведите «NO».

Ограничения:
1 ≤ T ≤ 30
1 ≤ | s | ≤ 10 ^ 16

Пример:
Входные данные:
1
аллергия аллергия

Выход:
НЕТ

Мой подход заключается в том, чтобы сначала проверить длину строк, если они не равны, то просто распечатать НЕТ и если они равны, то сортируйте строки и затем сравнивайте по элементам.

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

#include <iostream>
using namespace std;
#include<string>
#include<algorithm>
int main() {
int n, t=0;
cin>>n;
for(int i=0;i<n;i++)
{
string a,b;
cin>>a>>b;
cout<<"\n";
if(a.length()!=b.length())
{
cout<<"NO";
}
else
{
sort(a.begin(),a.end());
sort(b.begin(),b.end());
for(int i=0;i<a.length();i++)
{
if(a[i]!=b[i])
{
cout<<"NO";
break;
}
t++;
}
if(t==a.length())
{
cout<<"YES";
}
}
}

return 0;
}

-2

algorithm anagram c++onlinejudge string

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Ваш код, кажется, дает только 1 ответ, когда ожидается 2.
Проблема в том, что вы не сбрасываете t переменная;) Так что она всегда увеличивается.
Пример прогона: https://ideone.com/IYK6Ad

Входной тест:

2
aab baa
a a

Выход:

YES

Фиксированный код:

#include <iostream>
using namespace std;
#include<string>
#include<algorithm>
int main() {
int n, t=0;
cin>>n;
for(int i=0;i<n;i++)
{
string a,b;
cin>>a>>b;
if(a.length()!=b.length())
{
cout<<"NO\n";
}
else
{
sort(a.begin(),a.end());
sort(b.begin(),b.end());
if(a != b)
{
cout<<"NO\n";
}
else
{
cout<<"YES\n";
}
}
}

return 0;
}

Пример запуска

Некоторые намеки на улучшение этого алгоритма.
Пока мы рассматриваем только 1 контрольный пример для проверки анаграммы.

Так что в вашем случае у вас есть 2 * O(n * log n) complexity в основном из-за std::sort(Проверьте сложность)

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

Пройдет ли это, конечно, будет зависеть от того, насколько большими будут тестовые случаи и сколько тестовых случаев.

Идея улучшения:

Посчитайте каждый символ (мы можем использовать std::map<char,int> для этого, но доступ к элементам в карте также занимает некоторое время. Так что в нашем случае мы знаем что-то о входных данных, чтобы мы могли извлечь из этого пользу. Это должны быть данные ASCII, чтобы мы могли поместиться в фиксированный массив.)
Если количество конкретных символов отличается, мы знаем ответ!

За такое решение мы бы получили O(n+m) + O(min(n,m)) где n длина строки a а также m длина b, Довольно лучшая сложность.

Пример:

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

using namespace std;

int main()
{
int n;
cin>>n;
std::vector<int> aCountOfChars(256, 0);
std::vector<int> bCountOfChars(256, 0);

for(int i=0;i<n;i++)
{
string a,b;
cin>>a>>b;
std::vector<int> aCountOfChars(256, 0);
std::vector<int> bCountOfChars(256, 0);

for(int i=0;i<a.size();++i)
{
++aCountOfChars[a[i]];
}
for(int i=0;i<b.size();++i)
{
++bCountOfChars[b[i]];
}

if(aCountOfChars == bCountOfChars)
{
cout<<"YES\n";
}
else
{
cout<<"NO\n";
}
}
return 0;
}

Беги меня

Некоторые контрольные примеры для проверки:

7
a b
aab baa
a a
aaaaaaaaaaaaaaaaaaaaaaaaaaaaa b
aabba bbaaa
act tac
allergy allergic

Хорошая статья о такой проблеме

2