Групповые анаграммы


Сложный уровень средний
Часто спрашивают в Амазонка Facebook Google Microsoft
хеширования строка

Нам нужно найти групповые анаграммы данных слов. Это означает, что для каждого слова мы собираемся sort его и сохранить как ключ и исходный ввод, который не отсортирован как значение, и если какой-либо другой ввод имеет то же значение, что и ранее отсортированная строка, мы собираемся сохранить его с тем же ключом, но с другим значением, для этого vector передается как аргумент в функцию out, в которой мы собираемся выполнять все операции.

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

Пример: есть, есть, чай - анаграммы друг друга.

В этой задаче вам даны несколько слов. Ваша задача состоит в том, чтобы объединить в группу те слова, которые являются анаграммами друг друга.

Пример

Входной сигнал: есть, чай, загар, ела, нат, летучая мышь

Вывод: [есть, чай, ел], [загар, нат], [летучая мышь]

Алгоритм

  1. Объявите переменную карты mymap, вектор > переменная final_set.
  2. Внутри цикла возьмите входные значения в ключ и отсортируйте их
  3. Верните значение input [i] к ключу (который является отсортированной строкой) карты.
  4. Использование для каждого возврата значения в окончательный набор.
  5. Распечатайте окончательный набор.

объяснение

Сначала наш вклад задавать в котором все наши входные значения хранятся в качестве параметра. Здесь мы объявляем карту и вектор of vector переменная my_map и final_set соответственно. Переходим к циклу, который выполняет итерацию вектора до тех пор, пока не будет достигнут его размер. В этом цикле мы собираемся взять значение каждого индекса ввода в ключ.

Хранилище значений в ключе, которое мы собираемся отсортировать, чтобы мы могли проверить его как анаграмму, и поместить значение input [i] в ​​ключевое место карты, где ключ представляет собой отсортированную строку. Это будет продолжаться до тех пор, пока мы не переберем все значения во входном наборе. И сохраняя все ключевые значения на карте,

Затем мы собираемся добавить все значения my_map в окончательный вектор набора векторов. И, наконец, распечатайте его.

Пример

Предположим, ввод: [есть, чай, загар, ел, нат, летучая мышь]

Сортированный ключ = aet

Для aet в качестве ключа еда будет храниться как значение

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

После выполнения всех итераций:

aet (Отсортированная строка): [есть, чай, съесть] // пара ключ-значение

ant (Отсортированная строка): [tan, ant] // пара ключ-значение

abt (Отсортированная строка): [bat] // пара ключ-значение

И наконец, мы получили результат.

Реализация

Программа на C ++ для групповых анаграмм

#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;

vector<vector<string> > groupAnagrams(vector<string>& input_set)
{
    // the first value will hold the key,
    //the second vector is used to hold the multiple values.
    unordered_map<string, vector<string>> my_map;
    vector<vector<string> > final_set;

    for (int i = 0; i < input_set.size(); i++)
    {
        // take value at the index as a key
        string key = input_set[i];

        //sort the key
        sort(key.begin(), key.end());

        // add the value to that key
        my_map[key].push_back(input_set[i]);

    }

    for (auto n : my_map)
    {
        // add all the values in the map to the final set
        final_set.push_back(n.second);
    }

    return final_set;
}

int main()
{
    vector<string> input_set;
    input_set.push_back("eat");
    input_set.push_back("tea");
    input_set.push_back("tan");
    input_set.push_back("ate");
    input_set.push_back("nat");
    input_set.push_back("bat");

    vector<vector<string> > final_set =  groupAnagrams(input_set);

    // print the output
    cout<<" [ "<<endl;
    for (int i = 0; i < final_set.size(); i++)
    {
        if (final_set[i].size() > 0)
        {
            cout << "  [";
            for (int j = 0; j < final_set[i].size(); j++)
                cout<< final_set[i][j]<<" ";
            cout << "]";
        }
        cout<<endl;
    }
    cout<<" ] ";

    return 0;
}
[
 [bat ]
 [tan nat ]
 [eat tea ate ]
]

Программа на Java для групповых анаграмм

import java.util.*;
import java.util.stream.Collectors;

class findGroupAnagrams
{
  public static void getgroup(String[] words)
  {
    List<String> myList = Arrays.stream(words)
        .map(s -> s.toCharArray())
        .map(chars -> { Arrays.sort(chars); return new String(chars); })
        .collect(Collectors.toList());
    Map<String, List<Integer>> map = new HashMap<>();
    for (int i = 0; i < myList.size(); i++)
    {
      map.putIfAbsent(myList.get(i), new ArrayList<>());
      map.get(myList.get(i)).add(i);
    }
    for (var entry: map.entrySet()) {
      System.out.println(entry.getValue().stream()
              .map(index -> words[index])
              .collect(Collectors.toList()));
    }
  }
  public static void main(String[] args)
  {
    String[] input = {"eat","tea","tan","ate","nat","bat"};
    getgroup(input);
  }
}
[eat, tea, ate]
[bat]
[tan, nat]

Анализ сложности групповых анаграмм

Сложность времени

O (НМ) где N - количество слов, а M - максимальный символ, который имеет каждое слово.

Космическая сложность

О (Н + М) где N - количество слов, а M - максимальный символ, который имеет каждое слово.