गट अनाग्राम


अडचण पातळी मध्यम
वारंवार विचारले ऍमेझॉन फेसबुक Google मायक्रोसॉफ्ट
हॅशिंग अक्षरमाळा

आम्हाला दिलेल्या शब्दाचे गटशास्त्र शोधणे आवश्यक आहे. याचा अर्थ असा आहे की आपण ज्या प्रत्येक शब्दावर जात आहोत क्रमवारी हे ते एक की आणि मूळ इनपुट म्हणून संचयित करेल जे मूल्य म्हणून क्रमवारीत नाही आणि जर इतर कोणत्याही इनपुटचे पूर्वीचे क्रमवारी लावलेले स्ट्रिंगसारखेच मूल्य असेल तर आम्ही समान की वर संग्रहित करणार आहोत, परंतु भिन्न मूल्यासह, वेक्टर आउट आऊट फंक्शनमध्ये वितर्क म्हणून पास केला जातो ज्यामध्ये आपण सर्व ऑपरेशन्स करणार आहोत.

अनाग्राम: दुसर्‍या शब्दाची सर्व अक्षरे पुनर्रचना करून तयार केलेले शब्द अ‍ॅनाग्राम म्हणून ओळखले जातात.

उदाहरणः खाणे, खाणे, चहा हे एकमेकांचे अ‍ॅग्राम आहेत

या समस्येमध्ये आपल्याला काही शब्द दिले आहेत. आपले कार्य समूहातील त्या शब्दांची व्यवस्था करणे आहे जे एकमेकांचे अ‍ॅग्राम आहेत.

उदाहरण

इनपुट: खा, चहा, टॅन, खाल्ले, नट, बॅट

आउटपुट: [खा, चहा, खाल्ला], [टॅन, नाट], [बॅट]

अल्गोरिदम

  1. नकाशा व्हेरिएबल मायमॅप, एक वेक्टर घोषित करा > चल अंतिम_सेट.
  2. लूपच्या आत, इनपुट मूल्ये की मध्ये घ्या आणि त्या क्रमवारी लावा
  3. नकाशाच्या की (जे एक क्रमवारी लावलेले स्ट्रिंग आहे) वर इनपुटचे मूल्य परत ढकलणे.
  4. अंतिम सेटमध्ये प्रत्येक पुशबॅकसाठी मूल्य वापरणे.
  5. अंतिम संच मुद्रित करा.

स्पष्टीकरण

प्रथम, आमचे इनपुट संच ज्यामध्ये आमची सर्व इनपुट मूल्ये पॅरामीटर म्हणून पास केल्या आहेत. येथे आम्ही नकाशा घोषित करतो आणि वेक्टर अनुक्रमे माझे_मॅप आणि अंतिम_सेटचे वेक्टर व्हेरिएबल लूपमध्ये येत आहे जे वेक्टरचा आकार पूर्ण होईपर्यंत वेक्टरला पुनरावृत्ती करते. या लूपमध्ये आपण इनपुटच्या प्रत्येक निर्देशकाचे मूल्य की मध्ये घेणार आहोत.

आम्ही ज्या किल्लीमधील व्हॅल्यू स्टोअर त्यास क्रमवारी लावणार आहोत जेणेकरून आम्ही ते अनाग्राम म्हणून तपासू आणि इनपुटचे मूल्य [i] नकाशाच्या की ठिकाणी ठेवू, जिथे की एक सॉर्ट केलेली स्ट्रिंग आहे. जोपर्यंत आम्ही इनपुट सेटमधील सर्व मूल्ये पुनरावृत्ती करत नाही तोपर्यंत हे पुढे जाईल. आणि नकाशामध्ये सर्व की मूल्य संचयित करत आहे,

मग आपण माई-मॅपची सर्व व्हॅल्यूस वेक्टरच्या अंतिम सेट वेक्टरमध्ये समाविष्ट करणार आहोत. आणि शेवटी ते प्रिंट करा.

उदाहरण

समजा इनपुटः [खा, चहा, टॅन, खा, नाट, बॅट]

वर्गीकृत की = एट

एटसाठी की म्हणून खाणे मूल्य म्हणून संग्रहित केले जाईल

पुन्हा, चहाची क्रमवारी लावलेली कळ म्हणजे चहा म्हणून एक चावी आणि मूल्य म्हणून ठेवली जाईल.

सर्व पुनरावृत्ती केल्यानंतर:

एट (सॉर्ट केलेली स्ट्रिंग): [खा, चहा, खाल्ला] // की-व्हॅल्यू जोडी

मुंगी (सॉर्ट केलेली स्ट्रिंग): [टॅन, मुंगी) // की-व्हॅल्यू जोडी

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]

ग्रुप अनाग्रामसाठी गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एनएम) जिथे एन शब्दांची संख्या असते आणि एम प्रत्येक शब्दात असलेली अधिकतम वर्ण असते.

स्पेस कॉम्प्लेक्सिटी

ओ (एन + एम) जिथे एन शब्दांची संख्या असते आणि एम प्रत्येक शब्दात असलेली अधिकतम वर्ण असते.