Grupuj słowa z tym samym zestawem znaków

Poziom trudności Średni
Często zadawane pytania BlackRock Citrix IBM JP Morgan Laboratoria SAP Xome
Haszysz sznurodwiedzajacy 113

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

W przypadku problemu z grupowaniem słów z tym samym zestawem znaków podaliśmy listę słów z małymi literami. Zaimplementuj funkcję, aby znaleźć wszystkie słowa, które mają ten sam unikalny zestaw znaków.

Przykład

Wkład

Słowa [] = {„może”, „student”, „studenci”, „pies”, „uczennica”, „bóg”, „kot”, „akt”, „tab”, „nietoperz”, „przepływ”, „ wilk ”,„ jagnięta ”,„ ania ”,„ ignam ”,„ balsamy ”,„ zapętlony ”,„ pudel ”}

Wydajność

może, Amy, Yam,

student, studenci, studenci,

pies, bóg,

kot, akt,

zakładka, nietoperz,

przepływ, wilk,

jagnięta, balsamy,

zapętlony, pudel

Podejście 1: Brute force

Główny pomysł

Dla każdego słowa będziemy iterować po wszystkich słowach i znaleźć te słowa z tym samym zestawem znaków, a następnie je wydrukować.

Słowa, które już wydrukowaliśmy, oznaczymy je, abyśmy nie drukowali ich ponownie.

Algorytm dla Grupuj słowa z tym samym zestawem znaków

  1. Uruchom pętlę dla I w zakresie od 0 do n-1
    1. Jeśli długość słów [i] jest równa, pomiń ją, ponieważ już ją wydrukowaliśmy.
    2. Utwórz tablicę charSet1, która będzie przechowywać znaki obecne w słowach [i].
    3. Uruchom pętlę dla j w zakresie od I do n-1
      1. Utwórz tablicę charSet2, która będzie przechowywać znaki obecne w słowach [j]
      2. Jeśli charSet1 jest równe charSet2, wypisz słowa [j] i zamień słowa [j] na pusty łańcuch, co oznacza, że ​​wydrukowaliśmy ten ciąg.
    4. Powrót

Implementacja dla słów grupowych z tym samym zestawem znaków

Program w 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, 

Program 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,

Analiza złożoności

Złożoność czasowa

Używamy trzech zagnieżdżonych pętli, dwie z nich mają rozmiar N, a trzecia ma rozmiar długości sznurków. Jeśli przyjmiemy, że długość łańcucha wynosi L, to całkowita złożoność czasowa wynosi O (N * N * L).

Złożoność przestrzeni

Nie używamy dodatkowej przestrzeni, więc złożoność przestrzeni jest O (1).

Podejście 2: Używanie haszowania

Główny pomysł

Zrobimy klucz dla każdego ciąg który zapisze wszystkie różne znaki łańcucha w sposób posortowany. Następnie użyjemy skrótu do wszystkich słów z tym samym kluczem i wydrukujemy je na końcu.

Algorytm dla słów grupowych z tym samym zestawem znaków

  1. Zadeklaruj tablicę hash_table, która będzie przechowywać cały indeks wszystkich słów mających ten sam klucz.
  2. Stwórz funkcję makeKey, która zwróci klucz dla łańcucha.
  3. Uruchom pętlę dla I w zakresie od 0 do n-1
    1. Wstaw I w tablicy hash_table dla klucza „words [i]”.
  4. Iteruj po tablicy skrótów i drukuj ciągi z tym samym kluczem.
  5. Powrót

Zrozum na przykładzie

Słowa = {„może”, „student”, „studenci”, „pies”, „uczennica”, „bóg”, „kot”, „akt”, ”tab”, „nietoperz”, „przepływ”, „wilk” , „Jagnięta”, „amy”, „ignam”, „balsamy”, „zapętlone”, „pudel”}

Tabela skrótów będzie wyglądać następująco:

Grupuj słowa z tym samym zestawem znakówszpilka

Implementacja dla słów grupowych z tym samym zestawem znaków

Program w 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,

Program 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,

Analiza złożoności

Złożoność czasowa

Iterujemy po tablicy tylko raz, aw każdej iteracji generujemy klucz, wykonując iterację po ciągu. Tak więc, jeśli weźmiemy, że długość łańcucha wynosi L, to całkowita złożoność czasowa wynosi O (N * L).

Złożoność przestrzeni

Utrzymujemy tablicę skrótów, więc złożoność przestrzeni jest taka NA).

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »