Найти, если N строк являются анаграммами друг друга
В принципе у меня проблема с 2 подвопросами.
Первый вопрос: учитывая 2 строки, определите, являются ли они анаграммами.
Второе немного сложнее. У вас есть N строк, и вы должны определить, являются ли они анаграммами друг друга.
Я решил первый и напишу код ниже, но для второго я понятия не имею. Я думал, что можно как-то сделать это, прочитав N строк из массива строк, а затем использовать последовательность for, чтобы прочитать каждую из них и сравнить их, но я понятия не имею, как именно.
#include "stdafx.h"#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
string word1; string word2;
getline(cin,word1);
getline(cin,word2);
if(word1.length()==word2.length()){
sort(word1.begin(), word1.end());
sort(word2.begin(), word2.end());
if(word1==word2) cout<<"The words are anagrams of each other"<<endl;
else cout<<"The words are not anagrams of each other"<<endl;
}
else cout<<"The words are not the same length"<<endl;
return 0;
}
Решение
Выяснить, являются ли две строки анаграммами, чрезвычайно просто, особенно для набора символов ASCII. Наилучшим подходом является создание массива int размером 256. Пройдите первую строку и для каждого char ++ это int. Сделайте то же самое для второй строки и проверьте, не закончился ли массив тем же.
Расширить это до нескольких строк легко, так как если
а является анаграммой b и b является анаграммой c, тогда a является анаграммой c
Если вы делаете это с набором символов не ASCII, который больше, может быть хорошей идеей использовать хэш-карту вместо набора битов.
Другие решения
Если X является анаграммой Y и Z, то Y и Z также являются анаграммами
Итак, просто повторите вашу логику, самый простой подход: —
std::vector<std::string> words; //Use a vector
size_t i;
std::string word1,word2;
//Get words from standard input
std::copy(std::istream_iterator<std::string> (std::cin),
std::istream_iterator<std::string>(),
std::back_inserter(words));
word1=words[0]; //Check anagram with first word
sort(word1.begin(), word1.end());
for(i=1; i<words.size();i++)
{
word2=words[i];
sort(word2.begin(), word2.end());
if(word2!=word1)
break;
}
if(i==words.size())
std::cout<<"All Anagrams !";