Топтық анаграммалар


Күрделілік дәрежесі орта
Жиі кіреді Amazon Facebook Google Microsoft
Хэш String

Берілген сөздердің топтық анаграммаларын табуымыз керек. Бұл біз баратын әрбір сөз үшін білдіреді сорт оны мән ретінде сұрыпталмаған кілт және түпнұсқа енгізу ретінде сақтаңыз, егер басқа кірістің мәні бұрын сұрыпталған жолмен бірдей болса, біз оны сол кілтпен сақтаймыз, бірақ әр түрлі мәнмен, ол үшін вектор аргумент ретінде барлық операцияларды орындайтын функцияға беріледі.

Анаграммалар: Басқа сөздің барлық әріптерін қайта құру арқылы жасалған сөздер анаграмма деп аталады.

Мысалы: Тамақ, тамақ, шай бір-бірінің анаграммасы

Бұл мәселеде сізге бірнеше сөздер беріледі. Сіздің міндетіңіз - осы сөздерді бір-біріне анаграмма болатын топқа орналастыру.

мысал

Кіру: жеу, шай, тотығу, жеу, нат, жарқанат

Шығару: [тамақ, шай, жеді], [тан, нат], [жарқанат]

Алгоритм

  1. Картаның айнымалысын, векторын жарияла > айнымалы final_set.
  2. Ілмек ішіндегі енгізу мәндерін кілтпен қабылдап, оларды сұрыптаңыз
  3. [I] енгізу мәнін картаның кілтіне (ол сұрыпталған жол) қайтарыңыз.
  4. Әрбір басу үшін мәнді соңғы жиынтыққа пайдалану.
  5. Соңғы жиынтықты басып шығарыңыз.

Түсіндіру

Алдымен біздің пікіріміз жиынтық онда біздің барлық енгізілген мәндеріміз параметр ретінде сақталады. Мұнда біз картаны жариялаймыз және векторы сәйкесінше my_map және final_set векторларының айнымалысы. Вектордың өлшеміне жеткенше векторды қайталайтын циклге келу. Бұл циклде біз әрбір кіріс индексінің мәнін кілтке айналдырамыз.

Біз анаграмма ретінде тексере алатындай етіп кілттегі құндылықтар қоймасын сұрыптап, [i] енгізу мәнін картаның кілт орнына сұрыпталған жолға орналастырамыз. Бұл кіріс жиынындағы барлық мәндерді қайталағанға дейін жалғасады. Барлық негізгі мәндерді картада сақтау,

Содан кейін біз барлық векторлардың векторына my_map мәндерін қосамыз. Соңында оны басып шығарыңыз.

мысал

Кірісті делік: [жеу, шай, тотығу, жеу, нат, жарқанат]

Сұрыпталған кілт = aet

Aet үшін негізгі тағам ретінде құндылық сақталады

Тағы да, шайдың сұрыпталған кілті кілт ретінде сақталатын болады және шай сияқты құнды болады.

Барлық қайталауларды орындағаннан кейін:

aet (Сұрыпталған жол): [жеу, шай ішу] // негізгі мәндер жұбы

ant (Сұрыпталған жол): [күңгірт, құмырсқа] // кілт-мән жұбы

abt (Сұрыпталған жол): [бат] // кілттер мәні жұбы

Ақыр соңында, біз нәтиже аламыз.

Іске асыру

Топтық анаграммаларға арналған 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 (NM) Мұндағы N - сөздердің саны, M - әр сөздің максималды таңбасы.

Ғарыштың күрделілігі

O (N + M) Мұндағы N - сөздердің саны, M - әр сөздің максималды таңбасы.