Qrup anagramları

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Facebook google microsoft
Hashing SimBaxılıb 41

Verilən sözlərin qrup anaqramlarını tapmaq məcburiyyətindəyik. Bu, gedəcəyimiz hər bir söz üçün deməkdir cür onu bir dəyər kimi sıralanmayan bir açar və orijinal giriş kimi saxlayın və başqa hər hansı bir giriş əvvəlcədən sıralanmış bir sətirlə eyni dəyərə sahibdirsə, eyni açarda saxlayacağıq, lakin bunun üçün fərqli dəyərlə vektor bütün əməliyyatları aparacağımız funksiyaya arqument kimi ötürülür.

Anaqramlar: Başqa bir sözün hərflərini yenidən düzəldərək yaranan sözlər anaqram kimi tanınır.

Nümunə: Yeyin, yeyin, çay bir-birinin anaqramlarıdır

Bu problemdə sizə bəzi sözlər verilir. Sənin tapşırığın bu sözləri bir-birinin anaqramları olan bir qrupda yerləşdirməkdir.

misal

Input: yemək, çay, tan, yedim, nat, yarasa

Çıxış: [yemək, çay, yedim], [tan, nat], [yarasa]

Alqoritm

  1. Bir xəritə dəyişən mymap, bir vektor elan edin > dəyişən final_set.
  2. Bir döngənin daxilində giriş dəyərlərini açarda götürün və onları sıralayın
  3. [İ] giriş dəyərini xəritənin düyməsinə (sıralanmış bir sətir) geri qaytarın.
  4. Hər bir itələmə dəyərini son dəstə daxilində istifadə etmək.
  5. Son dəsti çap edin.

Izahat

Əvvəlcə girişimiz təyin etmək bütün giriş dəyərlərimizin parametr olaraq ötürüldüyündə saxlanılır. Burada bir xəritə elan edirik vektor sırasıyla my_map və final_set vektorlarının dəyişən. Vektorun ölçüsünə çatana qədər vektoru təkrarlayan döngəyə gəlir. Bu dövrdə, hər bir giriş indeksinin dəyərini bir açara çevirəcəyik.

Anaqram olaraq yoxlaya biləcəyimiz və giriş [i] dəyərini xəritənin açarın çeşidlənmiş bir sətir olduğu bir yerində yerləşdirə biləcəyimiz üçün ayıracağımız açardakı dəyər deposu. Bu, giriş dəstindəki bütün dəyərləri təkrarlayana qədər davam edəcəkdir. Və bütün əsas dəyəri xəritədə saxlamaq,

Sonra vektorların son set vektoruna my_map-in bütün dəyərlərini əlavə edəcəyik. Və nəhayət, onu çap edin.

misal

Fərz edək ki, giriş: [yemək, çay, tan, yedim, nat, yarasa]

Sıralanmış açar = aet

Aet üçün əsas yemək kimi bir dəyər olaraq saxlayacağıq

Yenə də çayın çeşidlənmiş açarı açar kimi saxlanacaq və çay kimi dəyər.

Bütün təkrarlamaları etdikdən sonra:

aet (Sortlanmış sətir): [yemək, çay, yedim] // əsas dəyər cütü

qarışqa (Sortlanmış sətir): [tan, qarışqa] // əsas dəyər cütü

abt (Sortlanmış sətir): [bat] // açar dəyər cütü

Və nəhayət, nəticəni əldə edirik.

Həyata keçirilməsi

Qrup Anagramları üçün C ++ proqramı

#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 ]
]

Qrup Anagramları üçün Java proqramı

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]

Qrup Anaqramları üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

O (NM) burada N - sözlərin sayı və M - hər sözün sahib olduğu maksimum simvol.

Kosmik Mürəkkəblik

O (N + M) burada N - sözlərin sayı və M - hər sözün sahib olduğu maksimum simvol.

Translate »