קבץ מילים עם אותה סט דמויות


רמת קושי בינוני
נשאל לעתים קרובות בלקרוק Citrix יבמ JP מורגן מעבדות SAP קסום
בליל מחרוזת

במילים קבוצתיות עם אותה קבוצה של תווים, נתנו רשימה של מילים באותיות קטנות. יישם פונקציה כדי למצוא את כל המילים בעלות אותה ערכת תווים ייחודית.

דוגמה

קֶלֶט

מילים [] = {"מאי", "סטודנט", "סטודנטים", "כלב", "סטודנטית", "אלוהים", "חתול", "מעשה", "כרטיסיה", "עטלף", "זרימה", " זאב "," כבשים "," איימי "," ים "," מזור "," לולאה "," פודל "}

תְפוּקָה

מאי, איימי, ים,

סטודנט, סטודנטים, סטודנטית,

כלב, אלוהים,

חתול, מעשה,

לשונית, עטלף,

לזרום, זאב,

כבשים, בלמים,

לולאה, פודל

גישה 1: כוח אכזרי

רעיון מרכזי

עבור כל מילה, נחזור על כל המילים ונמצא את אותן מילים באותה קבוצת תווים ואז נדפיס אותה.

המילים שכבר הדפסנו, נסמן אותן כדי שלא נדפיס אותן שוב.

אלגוריתם עבור קבץ מילים עם אותה סט דמויות

  1. הפעל לולאה עבור אני בטווח 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. הפעל לולאה עבור אני בטווח 0 עד n-1
    1. הכנס את I לטבלת hash למפתח 'מילים [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).

מורכבות בחלל

אנו שומרים על שולחן חשיש, כך שמורכבות החלל היא עַל).

הפניות