જૂથ એનાગ્રામ્સ


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એમેઝોન ફેસબુક Google માઈક્રોસોફ્ટ
હેશિંગ શબ્દમાળા

આપેલા શબ્દોનાં જૂથ એનાગ્રામ્સ આપણે શોધવાના છે. આનો અર્થ એ છે કે આપણે જઈએ છીએ તે દરેક શબ્દ માટે સૉર્ટ કરો તે અને તેને કી અને મૂળ ઇનપુટ તરીકે સંગ્રહિત કરે છે જે મૂલ્ય તરીકે સortedર્ટ કરેલું નથી અને જો કોઈ અન્ય ઇનપુટ સમાન મૂલ્ય ધરાવે છે જે અગાઉના સortedર્ટ કરેલા શબ્દમાળા જેવું છે, તો આપણે તે જ કી પર સંગ્રહિત કરીશું, પરંતુ વિવિધ મૂલ્ય સાથે, આ માટે, વેક્ટર આઉટ ફંક્શનમાં દલીલ તરીકે પસાર થાય છે જેમાં આપણે તમામ કામગીરી કરીશું.

એનાગ્રામ્સ: બીજા શબ્દના બધા અક્ષરોને ફરીથી ગોઠવીને જે શબ્દો બનાવવામાં આવ્યા છે તે એનેગ્રામ તરીકે ઓળખાય છે.

ઉદાહરણ: ખાવું, ખાધું, ચા એ એકબીજાના એનાગ્રામ છે

આ સમસ્યામાં, તમને કેટલાક શબ્દો આપવામાં આવે છે. તમારું કાર્ય એ શબ્દોને જૂથમાં ગોઠવવાનું છે જે એકબીજાના એનાગ્રામ્સ છે.

ઉદાહરણ

ઇનપુટ: ખાય, ચા, તન, ખાધું, નાટ, બેટ

આઉટપુટ: [ખાય, ચા, ખાવું], [તન, નાટ], [બેટ]

અલ્ગોરિધમ

  1. નકશો ચલ માયમેપ, વેક્ટર જાહેર કરો > ચલ અંતિમ_સેટ.
  2. લૂપની અંદર, ઇનપુટ મૂલ્યો કીમાં લો અને તેમને સ sortર્ટ કરો
  3. નકશાની કી (જે સ aર્ટિંગ સ્ટ્રિંગ છે) પર ઇનપુટનું મૂલ્ય પાછું દબાણ કરો.
  4. અંતિમ સેટમાં દરેક પુશબેક માટે મૂલ્યનો ઉપયોગ.
  5. અંતિમ સેટ છાપો.

સમજૂતી

શરૂઆતમાં, અમારું ઇનપુટ સમૂહ જેમાં અમારા બધા ઇનપુટ મૂલ્યો પેરામીટર તરીકે પાસ કરેલા છે. અહીં આપણે નકશા જાહેર કરીએ છીએ અને વેક્ટર અનુક્રમે મારા_મેપ અને અંતિમ_સેટના વેક્ટર ચલ લૂપમાં આવવું જે વેક્ટરનું કદ ન આવે ત્યાં સુધી વેક્ટરને પુનરાવર્તિત કરે છે. આ લૂપમાં, આપણે ઇનપુટના દરેક ઇન્ડેક્સનું મૂલ્ય કીમાં લઈ જઈશું.

અમે તેને કીમાં સ .ર્ટ કરવા જઈ રહ્યા છીએ તે કી મૂલ્ય સ્ટોર કે જેથી આપણે તેને એનાગ્રામ તરીકે તપાસી શકીએ, અને ઇનપુટની કિંમત [i] નકશાની કી જગ્યાએ મૂકી શકીએ, જ્યાં કી સ sર્ટ થયેલ શબ્દમાળા છે. જ્યાં સુધી આપણે ઇનપુટ સેટમાં તમામ કિંમતોને પુનરાવર્તિત નહીં કરીએ ત્યાં સુધી આ ચાલુ રહેશે. અને નકશામાં બધી કી કિંમત સંગ્રહિત કરી રહ્યા છીએ,

પછી આપણે વેક્ટરના અંતિમ સેટ વેક્ટરમાં માય_મેપની બધી કિંમતો ઉમેરવા જઈશું. અને અંતે, તેને છાપો.

ઉદાહરણ

ધારો ઇનપુટ: [ખાય, ચા, તાન, ખાવું, નાટ, બેટ]

સortedર્ટ કી = aet

કી માટે ખાય મૂલ્ય તરીકે સંગ્રહિત થાય છે

ફરીથી, ચાની છટણી કરેલી ચા એ ચાની ચાવી અને મૂલ્ય તરીકે સંગ્રહવા જઈ રહી છે.

બધી પુનરાવર્તનો કર્યા પછી:

aet (સ stringર્ટિંગ શબ્દમાળા): [ખાય, ચા, ખાવું] // કી-મૂલ્યની જોડી

કીડી (સ stringર્ટિંગ શબ્દમાળા): [ટેન, કીડી] // કી-મૂલ્યની જોડ

abt (સortedર્ટિંગ શબ્દમાળા): [બેટ] // કી-મૂલ્યની જોડ

અને અંતે, અમને આઉટપુટ મળે છે.

અમલીકરણ

ગ્રુપ એનાગ્રામ્સ માટે સી ++ પ્રોગ્રામ

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

જૂથ એનાગ્રામ્સ માટે જાવા પ્રોગ્રામ

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) જ્યાં એન શબ્દોની સંખ્યા છે અને એમ દરેક શબ્દનું મહત્તમ પાત્ર છે.

અવકાશ જટિલતા

ઓ (એન + એમ) જ્યાં એન શબ્દોની સંખ્યા છે અને એમ દરેક શબ્દનું મહત્તમ પાત્ર છે.