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


Рівень складності Medium
Часто запитують у Амазонка Facebook Google Microsoft
Хешування рядок

Ми маємо з’ясувати групові анаграми поданих слів. Це означає для кожного слова, яке ми збираємось сортувати він і зберігає його як ключ та оригінальний вхід, який не сортується як значення, і якщо будь-який інший вхід має таке саме значення, як і раніше відсортований рядок, ми будемо зберігати його під тим самим ключем, але з різним значенням, vector передається як аргумент у функцію out, в якій ми будемо виконувати всі операції.

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

Приклад: їсти, їсти, чай є анаграмами один одного

У цій задачі вам дано кілька слів. Ваше завдання - розташувати ці слова в групі, які є анаграмами один одного.

Приклад

Вхідний сигнал: їсти, чай, засмагати, їсти, нат, кажан

вихід: [їсти, чай, їв], [загар, нат], [кажан]

Алгоритм

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

Пояснення

Спочатку наш внесок комплект в якому всі наші вхідні значення зберігаються в переданому як параметр. Тут ми оголошуємо карту і вектор змінних векторів 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 - максимальний символ, який має кожне слово.

Складність простору

O (N + M) де N - кількість слів, а M - максимальний символ, який має кожне слово.