Групови анаграми


Ниво на трудност M
Често задавани в Амазонка Facebook Google Microsoft
хеширане Низ

Трябва да открием груповите анаграми на дадените думи. Това означава за всяка дума, към която ще отидем вид го съхранявайте като ключ и оригинален вход, който не е сортиран като стойност и ако някой друг вход има същата стойност като предишен сортиран низ, ще съхраняваме при същия ключ, но с различна стойност, за това, вектор се предава като аргумент във функция out, в която ще правим всички операции.

Анаграми: Думите, които са създадени чрез пренареждане на всички букви на друга дума, са известни като анаграми.

Пример: Яжте, ядете, чай са анаграми един на друг

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

Пример

Вход: яде, чай, тен, яде, nat, прилеп

Изход: [яде, чай, яде], [тен, nat], [прилеп]

алгоритъм

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

Обяснение

Отначало нашият принос определен в която всички наши входни стойности се съхраняват в предадени като параметър. Тук декларираме карта и вектор на вектори променлива съответно на my_map и final_set. Влизайки в цикъл, който повтаря вектора, докато се достигне размерът на вектора. В този цикъл ще вземем стойността на всеки индекс на входа в ключ.

Съхранението на стойността в ключа ще го сортираме, за да можем да го проверим като анаграма и да поставим стойността на input [i] в ​​ключово място на картата, където ключът е сортиран низ. Това ще продължи, докато не повторим всички стойности във входния набор. И съхраняване на цялата ключова стойност в картата,

След това ще добавим всички стойности на my_map в крайния набор от вектори на вектори. И накрая, отпечатайте го.

Пример

Да предположим, че въведете: [яде, чай, тен, яде, nat, прилеп]

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

За ает като ключово ядене ще се съхранява като стойност

Отново сортираният ключ на чая е, че ает ще съхранява като ключ и стойност като чай.

След като направите всички итерации:

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

ant (Сортиран низ): [тен, мравка] // двойка ключ-стойност

abt (Сортиран низ): [прилеп] // двойка ключ-стойност

И накрая получаваме изхода.

изпълнение

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 (NM) където N е броят на думите, а M е максималният знак, който всяка дума има.

Сложност на пространството

O (N + M) където N е броят на думите, а M е максималният знак, който всяка дума има.