Проверьте мой код анаграммы из собеседования в прошлом

Question

Некоторое время назад я задал следующий вопрос в качестве интервью и настолько сильно задохнулся от базового синтаксиса, что я не смог его продвинуть (как только адреналин включился, кодирование исчезло).

Учитывая список строк, вернуть список наборов строк, которые являются анаграммами входного набора. то есть "собака", "бог", "фу" должны возвращать {"собака", "бог"}. После этого я сам создал код для проверки работоспособности, и теперь он уже немного. Я бы приветствовал вклад, чтобы увидеть, пропустил ли я что-нибудь или мог бы сделать это намного эффективнее. Используйте это как шанс улучшить себя и изучить другие методы:

<code>
void Anagram::doWork(list input, list> &output)
{
  typedef list < pair < string, string>> SortType;
  SortType sortedInput;<br>
  // sort each string and pair it with the original
  for(list< string >::iterator i = input.begin(); i != input.end(); ++i)
  {
    string tempString(*i);
    std::sort(tempString.begin(), tempString.end());
    sortedInput.push_back(make_pair(*i, tempString));
  }<br>
  // Now step through the new sorted list
  for(SortType::iterator i = sortedInput.begin(); i != sortedInput.end();)
  {
    set< string > newSet;<br>
    // Assume (hope) we have a match and pre-add the first.
    newSet.insert(i->first);<br>
    // Set the secondary iterator one past the outside to prevent
    // matching the original
    SortType::iterator j = i;
    ++j;<br>
    while(j != sortedInput.end())
    {
      if(i->second == j->second)
      {
        // If the string matches, add it to the set and remove it
        // so that future searches need not worry about it
        newSet.insert(j->first);
        j = sortedInput.erase(j);
      }
      else
      {
        // else, next element
        ++j;
      }
    }<br>
    // If size is bigger than our original push, we have a match 
    // - save it to the output
    if(newSet.size() > 1)
    {
       output.push_back(newSet);
    }<br>
    // erase this element and update the iterator
    i = sortedInput.erase(i);
  }
}

Вот второй проход после просмотра комментариев и изучения немного больше:

<code>
void doBetterWork(list input, list> &output)
{
  typedef std::multimap< string, string > SortedInputType;
  SortedInputType sortedInput;
  vector< string > sortedNames;<br>
  for(vector< string >::iterator i = input.begin(); i != input.end(); ++i)
  {
    string tempString(*i);
    std::sort(tempString.begin(), tempString.end());
    sortedInput.insert(make_pair(tempString, *i));
    sortedNames.push_back(tempString);
  }<br>
  for(list< string >::iterator i = sortedNames.begin(); i != sortedNames.end(); ++i)
  {
    pair< SortedInputType::iterator,SortedInputType::iterator > bounds;
    bounds = sortedInput.equal_range(*i);<br>
    set< string > newSet;
    for(SortedInputType::iterator j = bounds.first; j != bounds.second; ++j)
    {
      newSet.insert(j->second);
    }<br>
    if(newSet.size() > 1)
    {
      output.push_back(newSet);
    }<br>
    sortedInput.erase(bounds.first, bounds.second);
  }
}</p>

<p>

Answer 1

Лучший способ сгруппировать анаграммы - сопоставить строки с каким-либо представлением гистограммы.

 FUNCTION histogram
 [input] -> [output]

 "dog"   -> (1xd, 1xg, 1xo)
 "god"   -> (1xd, 1xg, 1xo)
 "foo"   -> (1xf, 2xo)

По сути, при линейном сканировании строки вы можете получить гистограмму, показывающую, сколько каждой буквы она содержит. Небольшой конечный алфавит делает это еще проще (например, с A-Z, у вас просто есть массив из 26 чисел, по одному на каждую букву).

Теперь анаграммы - это просто слова с одинаковой гистограммой.

Тогда вы можете иметь структуру данных с несколькими картами, которая отображает гистограмму в список слов, имеющих эту гистограмму.

MULTIMAP
[key]           => [set of values]

(1xd, 1xg, 1xo) => { "dog", "god" }
(1xf, 2xo)      => { "foo" }

Трюк с канонической формой

Вместо работы с гистограммами, вы также можете работать с "канонической формой" строк. По сути, вы определяете для каждой строки ее каноническую форму и два слова являются анаграммами, если они имеют одинаковую каноническую форму.

Одна удобная каноническая форма состоит в том, чтобы буквы в строке располагались в отсортированном порядке.

FUNCTION canonize
[input]  -> [output]

"dog"    -> "dgo"
"god"    -> "dgo"
"abracadabra" -> "aaaaabbcdrr"

Обратите внимание, что это всего лишь один шаг после гистограммного подхода: вы по существу делаете подсчет сортировки для сортировки букв.

Это наиболее практичное решение на вашем языке программирования для вашей проблемы.

Сложность

Создание гистограммы / канонической формы слова практически O(1) (конечный размер алфавита, конечная максимальная длина слова).

При хорошей реализации хеша get и put на мультикарте равны O(1).

Вы можете даже иметь несколько мультикарт, по одному на каждую длину слова.

Если есть N слов, следовательно, помещение всех слов в мультикарты будет O(N); затем вывод каждой группы анаграмм просто выводит значения в мультикартах. Это тоже можно сделать в O(N).

Это, безусловно, лучше, чем проверять, являются ли каждая пара слов анаграммами (алгоритм O(N^2)).

Answer 2

Алгоритм проверки того, являются ли две строки анаграммами друг друга, выглядит следующим образом

1. преобразовать две строки таким образом, чтобы они содержали только букву (потому что свекровь и женщина-гитлер - это также анаграмма). Также для двух строк одинаковые значения означают, что обе строки находятся в верхнем регистре или в нижнем регистре.

2. теперь сортируем символы в обеих строках.

3. сравнение двух строк, если они равны, означает, что они являются анаграммами друг друга

Вот код этого алгоритма

bool checkanagrams(string first,string second)
{

    string tempfirst,tempsecond;    
    int countfirst  = 0;  
    int countsecond = 0;        
   // only storing characters removing other junk things  like -
   for(int i=0;i<first.length();i++)
   {
      if(isalpha(first[i])
      { 
        tempfirst[countfirst] =first[i];
    countfirst++; 
      }

   }
   for(int i=0;i<second.length();i++)
   {
      if(isalpha(second[i])
      { 
        tempsecond[countsecond] =second[i];
    countsecond++; 
      }        

   } 
   sort(tempfirst.begin(),tempfirst.end());  
   sort(tempsecond.begin(),tempsecond.end());
   if(!strcmp(tempfirst.c_str(),tempsecond.c_str())
    return true;
   else
    return false;     

}

Answer 3

Я просто отнесусь к ней как к бесплатной функции get_anagrams, поскольку class Anagram, похоже, больше ничего не делает.

Выбор list и set не лучшечем что-либо еще, поэтому, пока я в этом, я сделаю их обоих vector.На самом деле, выход может быть только одной последовательностью.Назовите это anagram_sort.Я возьму спецификации «список» и «набор» в качестве базовых конструкций, а не буквальных шаблонов классов.Также «данный… возврат» можно свободно интерпретировать как изменение ввода на месте.Вызывающий может создать копию, если ему нравится.

struct anagram_less { bool operator()( string const &l, string const &r ) {
    string sl( l ), sr( r );
    sort( sl.begin(), sl.end() );
    sort( sr.begin(), sr.end() );
    return sl < sr;
} };

void anagram_sort( vector< string > &v ) { // "the answer"
    sort( v.begin(), v.end(), anagram_less );
} // 10 lines

   // usage:

void print_anagrams( vector< string > &&v ) { // destructive => use rvalue ref
    anagram_sort( v );

    for ( vector< string >::iterator i = v.begin(); i != v.end(); /*++i*/ ) {

        vector< string >::iterator e // find end of run of anagrams
            = adjacent_find( i, v.end(), anagram_less() );
        if ( e != v.end() ) ++ e; // usually need this after adjacent_find :v(

        cout << "( ";
        for ( ; i != e; ++ i ) {
            cout << * i << " ";
        }
        cout << ")" << endl;
    }
}

Это неоптимально, так как повторяет сортировку слов.Я бы предпочел сократить вопрос интервью, чем сделать что-то быстрое «на бумаге».

Чтобы выжать этот последний кусочек исполнения, я бы, вероятно, сделал копию ввода с серийным номером.-привязанные индексы, сортировка символов строк, сортировка строк, а затем использование индексов для переупорядочения входного вектора с использованием этого алгоритма .Конечное время выполнения с низким коэффициентом O (n log n), как и должно быть.

Answer 4

Я бы положил все в хеш-таблицу. Затем для каждой строки я возвращаю ее и проверяю, существует ли она в хеш-таблице, если это так, возвращаю как обратную строку, так и себя в наборе.

Этот подход также находит палиндромы в наборе.