Найдите, являются ли 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;
}

c++ string anagram
person bamtheboozle    schedule 17.10.2013    source источник
comment
если string1 является анаграммой string2 и string3, то string2 и string3 определенно являются анаграммами друг друга   -  person digital_revenant    schedule 17.10.2013
comment
О, да. Простите за это. Я потерялся во всем этом. Даже так. Я не могу понять, как читать массив строк. Все, что я искал, использует указатели, а я еще не изучил их.   -  person bamtheboozle    schedule 17.10.2013
comment
@DragoşPaulMarinescu сортировка строк для проверки крайне неэффективна и не требует проверки моего ответа.   -  person aaronman    schedule 17.10.2013

Ответы (2)


arrow_upward
0
arrow_downward

Определить, являются ли две строки анаграммами, чрезвычайно просто, особенно для набора символов ASCII. Наилучший подход — создать массив int размером 256. Пройтись по первой строке и для каждого char++ этого int. Сделайте то же самое для второй строки и проверьте, получился ли массив таким же.

Расширить это до нескольких строк легко, так как если

a является анаграммой b и b является анаграммой c, тогда a является анаграммой c

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

person aaronman    schedule 17.10.2013
comment
Я попробую ваше решение позже сегодня. Сначала я хотел бы решить это, если это возможно, на основе того, что я уже закодировал для первого решения. Было бы неплохо принять ваше решение в качестве задачи. - person bamtheboozle; 17.10.2013
comment
@DragoşPaulMarinescu IMO, это довольно просто, если бы вы на самом деле написали свой собственный вид, ваше решение на самом деле потребовало бы гораздо больше усилий, я не хочу просто давать вам код, но я сделал это примерно в 10 строках кода, так что это не так сложно - person aaronman; 17.10.2013

arrow_upward
0
arrow_downward

Если 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 !";
person P0W    schedule 17.10.2013
comment
Когда я пишу std::vector‹std::string› слова; компилятор выдает ошибку, говоря, что пространство имен std не имеет вектора-члена. Раньше я действительно не использовал векторы, поэтому для меня это совершенно новый мир. Извините, что показался нубом :( - person bamtheboozle; 17.10.2013
comment
@DragoşPaulMarinescu Вам необходимо включить правильные заголовки. См. Здесь - person P0W; 17.10.2013
comment
Упс, забыл включить #include ‹vector› - person bamtheboozle; 17.10.2013
comment
Пытался использовать код в Visual Studio, но получаю ошибку: puu.sh/4Spdn.png - person bamtheboozle; 17.10.2013
comment
@DragoşPaulMarinescu #include<string> И прежде чем вы спросите, как перестать вводить слова из консоли, это Ctrl+Z или просто F6, это означает конец потока. - person P0W; 17.10.2013
comment
Красивый. Я знал о команде ctrl+z, но она не приходила мне в голову, хех. Работает нормально, теперь нужно изучить и понять все, что там есть :) - person bamtheboozle; 17.10.2013
comment
Кажется, что программа работает с некоторыми анаграммами, а для некоторых она вводит, что они не являются анаграммами, несмотря на то, что они являются анаграммами. Например, abc, bac, cab работают, а pow, wop, owp — нет. - person bamtheboozle; 17.10.2013