Тестирование Анаграммы

Question

Тестирование Анаграммы

Моя программа anagram прекрасно работает в моем dev-cpp, но в любом онлайн-тестере выдает неправильный ответ на любую тестовую anagram. Кто-нибудь может мне помочь?

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

int main()
{

char input1[10000];
char input2[10000];
cin >> input1;
getchar();
cin >> input2;
getchar();

int leng;
leng = strlen(input1);
bool output[leng];

for(int i=0; i<leng; i++){
for(int y=0; y<leng; y++){
if( input1[i] == input2[y] ){
output[i] = true;
}
}
}

for(int o=0; o<leng; o++ ){
if( (o+1) == leng){
if( output[o] == true){
cout << "ano" << endl;
break;
}
}else if(output[o] == true) {
continue;
}
cout << "nie" << endl;
break;
}getchar();
return 0;
}

1

anagram c++

Решение

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

Вместо того, чтобы пытаться изобретать велосипед, есть аккуратная функция is_permutation в <algorithm> это может сделать эту проблему тривиальной. ,

#include <algorithm>

bool isAnagram(std::string a, std::string b) {
if(a.size() == b.size()) {
return std::is_permutation ( a.begin(), a.end(), b.begin(), [](char x, char y){return std::tolower(x) == std::tolower(y);} );
}
return false;
}

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

1

Источник

Accepted Answer

У вас есть проблемы с вашим алгоритмом. Представьте себе следующий сценарий:

Input1: ab
Input2: cdefab

Ваш алгоритм вернет OK, потому что он будет только проверять, что & b символов input1 присутствуют в input2.

Та же проблема с примером, например:

Input1: aaaaaa
Input2: a

Или же:

Input1: aaaab
Input2: bbbba

Вы можете изменить свой алгоритм следующим образом:

Подсчет символов с использованием массива 256 (индекс вашего символа в ASCII) int инициализируется до 0. Увеличение для input1 и уменьшение для input2, в конце ваш массив должен быть заполнен 0. O (n) algo
Сортировка ваших двух входных данных и сравнение их символ за символом. O (n ^ 2) алгоритм

Вы можете найти более подробную информацию о тех, кто Вот.

0