குழு அனகிராம்ஸ்


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது அமேசான் பேஸ்புக் கூகிள் மைக்ரோசாப்ட்
ஹேஷிங் சரம்

கொடுக்கப்பட்ட சொற்களின் குழு அனகிராம்களை நாம் கண்டுபிடிக்க வேண்டும். இதன் பொருள் நாம் போகும் ஒவ்வொரு வார்த்தைக்கும் வகையான அதை ஒரு முக்கிய மற்றும் அசல் உள்ளீடாக சேமித்து வைக்கவும், இது ஒரு மதிப்பாக வரிசைப்படுத்தப்படவில்லை மற்றும் வேறு எந்த உள்ளீடும் முன்பு வரிசைப்படுத்தப்பட்ட சரத்தின் அதே மதிப்பைக் கொண்டிருந்தால், அதே விசையில் சேமிக்கப் போகிறோம், ஆனால் வெவ்வேறு மதிப்புடன், இதற்காக, திசையன் ஒரு செயல்பாடாக அவுட் செயல்பாட்டிற்கு அனுப்பப்படுகிறது, இதில் நாம் அனைத்து செயல்பாடுகளையும் செய்யப் போகிறோம்.

அனகிராம்ஸ்: வேறொரு வார்த்தையின் அனைத்து எழுத்துக்களையும் மறுசீரமைப்பதன் மூலம் உருவாக்கப்படும் சொற்கள் அனகிராம் என அழைக்கப்படுகின்றன.

எடுத்துக்காட்டு: சாப்பிடுங்கள், சாப்பிட்டோம், தேநீர் என்பது ஒருவருக்கொருவர் அனகிராம்கள்

இந்த சிக்கலில், உங்களுக்கு சில வார்த்தைகள் வழங்கப்படுகின்றன. ஒருவருக்கொருவர் அனகிராம்களாக இருக்கும் அந்த வார்த்தைகளை ஒரு குழுவில் ஏற்பாடு செய்வதே உங்கள் பணி.

உதாரணமாக

உள்ளீடு: சாப்பிடு, தேநீர், பழுப்பு, சாப்பிட்டது, நாட், பேட்

வெளியீடு: [சாப்பிடு, தேநீர், சாப்பிட்டேன்], [பழுப்பு, நாட்], [மட்டை]

அல்காரிதம்

  1. வரைபட மாறி மைமாப்பை, ஒரு திசையன் என்று அறிவிக்கவும் > மாறி இறுதி_செட்.
  2. ஒரு வட்டத்திற்குள், உள்ளீட்டு மதிப்புகளை விசையில் எடுத்து அவற்றை வரிசைப்படுத்தவும்
  3. உள்ளீட்டின் மதிப்பை [i] வரைபடத்தின் விசைக்கு (இது ஒரு வரிசைப்படுத்தப்பட்ட சரம்) பின்னுக்குத் தள்ளவும்.
  4. ஒவ்வொரு புஷ்பேக்கிற்கும் இறுதி தொகுப்பில் மதிப்பைப் பயன்படுத்துதல்.
  5. இறுதி தொகுப்பை அச்சிடுக.

விளக்கம்

முதலில், எங்கள் உள்ளீடு தொகுப்பு இதில் எங்கள் உள்ளீட்டு மதிப்புகள் அனைத்தும் ஒரு அளவுருவாக அனுப்பப்படுகின்றன. இங்கே நாம் ஒரு வரைபடத்தை அறிவிக்கிறோம் மற்றும் திசையன் முறையே my_map மற்றும் final_set இன் திசையன்களின் மாறி. திசையனின் அளவை அடையும் வரை திசையனை மீண்டும் இயக்கும் லூப்பிற்கு வருவது. இந்த சுழற்சியில், உள்ளீட்டின் ஒவ்வொரு குறியீட்டின் மதிப்பையும் ஒரு விசையில் எடுக்கப் போகிறோம்.

விசையில் உள்ள மதிப்புக் கடை அதை வரிசைப்படுத்தப் போகிறோம், இதன்மூலம் அதை ஒரு அனகிராம் என சரிபார்க்கவும், உள்ளீட்டின் மதிப்பை [i] வரைபடத்தின் முக்கிய இடத்தில் வைக்கவும், அங்கு விசை ஒரு வரிசைப்படுத்தப்பட்ட சரம். உள்ளீட்டு தொகுப்பில் உள்ள அனைத்து மதிப்புகளையும் மீண்டும் கூறும் வரை இது தொடரும். மேலும் அனைத்து முக்கிய மதிப்புகளையும் வரைபடத்தில் சேமிக்கிறது,

பின்னர் வெக்டார்களின் இறுதி தொகுப்பு திசையனில் my_map இன் அனைத்து மதிப்புகளையும் சேர்க்க உள்ளோம். இறுதியாக, அதை அச்சிடுங்கள்.

உதாரணமாக

உள்ளீடு என்று வைத்துக்கொள்வோம்: [சாப்பிடு, தேநீர், பழுப்பு, சாப்பிட்டது, நாட், பேட்]

வரிசைப்படுத்தப்பட்ட விசை = aet

ஒரு முக்கிய உணவாக ஏட் ஒரு மதிப்பாக சேமிக்க போகிறது

மீண்டும், தேயிலை வரிசைப்படுத்தப்பட்ட விசையானது ஒரு முக்கிய மற்றும் தேயிலை மதிப்பாக சேமிக்கப் போகிறது.

அனைத்து மறு செய்கைகளையும் செய்த பிறகு:

aet (வரிசைப்படுத்தப்பட்ட சரம்): [சாப்பிடு, தேநீர், சாப்பிட்டது] // விசை மதிப்பு ஜோடி

எறும்பு (வரிசைப்படுத்தப்பட்ட சரம்): [பழுப்பு, எறும்பு] // விசை மதிப்பு ஜோடி

abt (வரிசைப்படுத்தப்பட்ட சரம்): [மட்டை] // விசை மதிப்பு ஜோடி

கடைசியாக, வெளியீட்டைப் பெறுகிறோம்.

நடைமுறைப்படுத்தல்

குழு அனகிராம்களுக்கான சி ++ நிரல்

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

குழு அனகிராம்களுக்கான சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (என்.எம்) இங்கு N என்பது சொற்களின் எண்ணிக்கை மற்றும் M என்பது ஒவ்வொரு வார்த்தையின் அதிகபட்ச எழுத்து.

விண்வெளி சிக்கலானது

O (N + M) இங்கு N என்பது சொற்களின் எண்ணிக்கை மற்றும் M என்பது ஒவ்வொரு வார்த்தையின் அதிகபட்ச எழுத்து.