Групуйце словы з аднолькавым наборам знакаў


Узровень складанасці серада
Часта пытаюцца ў BlackRock Citrix IBM JP Morgan Лабараторыі SAP Xome
гашыш Радок

У групе слоў з аднолькавым наборам знакаў мы прывялі спіс слоў з малых літар. Рэалізаваць функцыю, каб знайсці ўсе словы, якія маюць аднолькавы набор унікальных сімвалаў.

Прыклад

уваход

Словы [] = {"можа", "студэнт", "студэнты", "сабака", "студэнты", "бог", "кошка", "дзейнічаць", "укладка", "кажан", "паток", " воўк "," ягняты "," амі "," ямс "," бальзамы "," пятля "," пудзель "}

выхад

можа, Эмі, ям,

студэнт, студэнты, студэнты,

сабака, божа,

кот, дзейнічай,

ўкладка, кажан,

паток, воўк,

ягняты, бальзамы,

пятля, пудзель

Падыход 1: Грубая сіла

Галоўная ідэя

Для кожнага слова мы перабярэм усе словы і знойдзем гэтыя словы з аднолькавым наборам знакаў, а потым надрукуем яго.

Словы, якія мы ўжо надрукавалі, мы пазначым, каб больш не друкавалі.

Алгарытм для Групуйце словы з аднолькавым наборам знакаў

  1. Запусціце цыкл для I у дыяпазоне ад 0 да n-1
    1. Калі даўжыня слоў [i] роўная, прапусціце, бо мы яе ўжо надрукавалі.
    2. Зрабіце масіў charSet1, які будзе захоўваць сімвалы, якія прысутнічаюць у словах [i].
    3. Выканайце цыкл для j у дыяпазоне ад I да n-1
      1. Зрабіце масіў charSet2, які будзе захоўваць сімвалы, якія прысутнічаюць у словах [j]
      2. Калі charSet1 роўны charSet2, то надрукуйце словы [j] і зменіце словы [j] на пусты радок, які азначае, што мы надрукавалі гэты радок.
    4. Вяртаць

Рэалізацыя для групавых слоў з аднолькавым наборам знакаў

Праграма C ++

#include<bits/stdc++.h>
using namespace std;
void wordsWithSameSetOfchar(vector<string>& words)
{
    int n=words.size();
    for(int i=0;i<n;i++)
    {
        if(words[i].length()==0)
        {
            continue;
        }
        vector<bool> charSet1(26,false);
        for(auto ele:words[i])
        {
            charSet1[ele-'a']=true;
        }
        for(int j=i;j<n;j++)
        {
            vector<bool> charSet2(26,false);
            for(auto ele:words[j])
            {
                charSet2[ele-'a']=true;
            }
            if(charSet2==charSet1)
            {
                cout<<words[j]<<", ";
                words[j]="";
            }
        }
        cout<<endl;
    }
    return;
}
int main()
{
    vector<string> words={ "may", "student", "students", "dog","studentssess", "god", "cat", "act","tab", "bat", "flow", "wolf", "lambs","amy", "yam", "balms", "looped", "poodle"};
    wordsWithSameSetOfchar(words);    
    return 0;
}
may, amy, yam, 
student, students, studentssess, 
dog, god, 
cat, act, 
tab, bat, 
flow, wolf, 
lambs, balms, 
looped, poodle, 

Праграма JAVA

import java.util.*;
public class Main
{
    static void wordsWithSameSetOfchar(String words[])
    {
        int n=words.length;
        for(int i=0;i<n;i++)
        {
            if(words[i].length()==0)
            {
                continue;
            }
            boolean[] charSet1 = new boolean[26];
            for(int l=0;l<words[i].length();l++)
            {
                charSet1[words[i].charAt(l)-'a']=true;
            }
            for(int j=i;j<n;j++)
            {
                boolean[] charSet2 = new boolean[26];
                for(int l=0;l<words[j].length();l++)
                {
                    charSet2[words[j].charAt(l)-'a']=true;
                }
                if(Arrays.equals(charSet2,charSet1))
                {
                    System.out.print(words[j]+", ");
                    words[j]="";
                }
            }
            System.out.println();
        }
        return;
    }
  public static void main(String[] args) {
    String words[]={ "may", "student", "students", "dog","studentssess", "god", "cat", "act","tab", "bat", "flow", "wolf", "lambs","amy", "yam", "balms", "looped", "poodle"};
    wordsWithSameSetOfchar(words);
  }
}
may, amy, yam, 
student, students, studentssess, 
dog, god, 
cat, act, 
tab, bat, 
flow, wolf, 
lambs, balms, 
looped, poodle,

Аналіз складанасці

Часовая складанасць

Мы выкарыстоўваем тры ўкладзеныя завесы, дзве з іх маюць памер N, а трэцяя мае памер даўжыні радкоў. Калі прыняць даўжыню радка за L, то агульная складанасць часу роўная O (N * N * L).

Касмічная складанасць

Мы не выкарыстоўваем лішняе месца, таму касмічная складанасць O (1).

Падыход 2: Выкарыстанне хэшавання

Галоўная ідэя

Мы зробім ключ для кожнага радок які будзе адсартаваць усе розныя сімвалы радка. Пасля гэтага мы будзем выкарыстоўваць хэшаванне ўсіх слоў з той самай клавішай і ў выніку надрукуем іх.

Алгарытм групавых слоў з аднолькавым наборам знакаў

  1. Абвясціце hash_table, які будзе захоўваць увесь індэкс усіх слоў, якія маюць адзін і той жа ключ.
  2. Зрабіце функцыю makeKey, якая верне ключ для радка.
  3. Запусціце цыкл для I у дыяпазоне ад 0 да n-1
    1. Устаўце I у хэш-табліцу для ключа "словы [i]".
  4. Перабірайце хэш-табліцу і раздрукоўвайце радкі тым самым ключом.
  5. Вяртаць

Зразумейце на прыкладзе

Словы = {"май", "студэнт", "студэнты", "сабака", "студэнты", "бог", "кот", "дзейнічаць", "укладка", "кажан", "паток", "воўк" , «Ягняты», «амі», «ямс», «бальзамы», «пятля», «пудзель»}

Хэш-табліца будзе выглядаць так:

Групуйце словы з аднолькавым наборам знакаў

Рэалізацыя для групавых слоў з аднолькавым наборам знакаў

Праграма C ++

#include<bits/stdc++.h>
using namespace std;
string makeKey(string& word)
{
    string key;
    vector<bool> charSet(26,false);
    for(auto ele:word)
    {
        charSet[ele-'a']=true;
    }
    for(int i=0;i<26;i++)
    {
        if(charSet[i])
        {
            key+=(char)(i+'a');
        }
    }
    return key;
}
void wordsWithSameSetOfchar(vector<string>& words)
{
    int n=words.size();
    unordered_map<string,vector<int>> hash_table;
    for(int i=0;i<n;i++)
    {
        hash_table[makeKey(words[i])].push_back(i);
    }
    for(auto keys:hash_table)
    {
        for(auto index:keys.second)
        {
            cout<<words[index]<<", ";
        }
        cout<<endl;
    }
    return;
}
int main()
{
        vector<string> words={ "may", "student", "students", "dog","studentssess", "god", "cat", "act","tab", "bat", "flow", "wolf", "lambs","amy", "yam", "balms", "looped", "poodle"};
    wordsWithSameSetOfchar(words);    
    return 0;
}
looped, poodle, 
student, students, studentssess, 
may, amy, yam, 
dog, god, 
cat, act, 
tab, bat, 
lambs, balms, 
flow, wolf,

Праграма JAVA

import java.util.*;
import java.util.Map.Entry; 
public class Main
{
    static String makekey(String word)
    {
        boolean[] charSet = new boolean[26];
        for(int l=0;l<word.length();l++)
        {
            charSet[word.charAt(l)-'a']=true;
        }
        String key="";
        for(int i=0;i<26;i++)
        {
            if(charSet[i])
            {
                key+=(char)(i+'a');
            }
        }
        return key;
    }
    static void wordsWithSameSetOfchar(String words[])
    {
        int n=words.length;
        HashMap<String, ArrayList<Integer>> hash_table = new HashMap<>(); 
    for (int i=0; i<n; i++) 
    { 
      String key = makekey(words[i]); 
      if(hash_table.containsKey(key)) 
      { 
        ArrayList<Integer> temp = hash_table.get(key); 
        temp.add(i); 
        hash_table.put(key, temp); 
      } 
      else
      { 
        ArrayList<Integer> temp = new ArrayList<>(); 
        temp.add(i); 
        hash_table.put(key, temp); 
      } 
    } 
    for (Entry<String, ArrayList<Integer>> keys : hash_table.entrySet()) 
    { 
      ArrayList<Integer> indices =keys.getValue(); 
      for (Integer index:indices) 
        System.out.print( words[index] + ", "); 
      System.out.println(); 
    } 
        return;
    }
  public static void main(String[] args) {
    String words[]={ "may", "student", "students", "dog","studentssess", "god", "cat", "act","tab", "bat", "flow", "wolf", "lambs","amy", "yam", "balms", "looped", "poodle"};
    wordsWithSameSetOfchar(words);
  }
}
student, students, studentssess, 
tab, bat, 
cat, act, 
lambs, balms, 
may, amy, yam, 
looped, poodle, 
dog, god, 
flow, wolf,

Аналіз складанасці

Часовая складанасць

Мы праводзім ітэрацыю па масіве толькі адзін раз, і ў кожнай ітэрацыі мы ствараем ключ, перабіраючы радок. Такім чынам, калі прыняць даўжыню радка за L, то агульная складанасць часу роўная O (N * L).

Касмічная складанасць

Мы падтрымліваем хэш-табліцу, таму касмічная складанасць O (N).

Спасылкі