동일한 문자 집합을 가진 그룹 단어

난이도 중급
자주 묻는 질문 BlackRock 시트릭스 IBM JP 모건 SAP 연구소
해시 조회수 39

동일한 문자 집합을 가진 단어 그룹 문제에서 소문자로 된 단어 목록을 제공했습니다. 동일한 고유 문자 집합을 가진 모든 단어를 찾는 함수를 구현합니다.

입력

Words [] = {“may”,“student”,“students”,“dog”,”studentssess”,“god”,“cat”,“act”,”tab”,“bat”,“flow”,“ wolf ","lambs ","amy ","yam ","balms ","looped ","poodle "}

산출

메이, 에이미, 얌,

학생, 학생, 학생

개, 신,

고양이, 행동,

탭, 박쥐,

흐름, 늑대,

양, 발삼,

루프, 푸들

접근 방식 1 : 무차별 대입

주요 아이디어

각 단어에 대해 모든 단어를 반복하고 동일한 문자 집합을 가진 단어를 찾은 다음 인쇄합니다.

이미 인쇄 한 단어는 다시 인쇄하지 않도록 표시합니다.

에 대한 알고리즘 동일한 문자 집합을 가진 그룹 단어

  1. 0에서 n-1 사이의 I에 대해 루프 실행
    1. 단어 [i]의 길이가 같으면 이미 인쇄 했으므로 건너 뜁니다.
    2. 단어 [i]에있는 문자를 저장할 배열 charSet1을 만듭니다.
    3. I ~ n-1 범위에서 j에 대해 루프 실행
      1. 단어 [j]에있는 문자를 저장할 배열 charSet2를 만듭니다.
      2. charSet1이 charSet2와 같으면 word [j]를 인쇄하고 words [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 사이의 I에 대해 루프 실행
    1. 'words [i]'의 키에 대한 hash_table에 I를 삽입합니다.
  4. 해시 테이블을 반복하고 동일한 키로 문자열을 인쇄합니다.
  5. 반품

예를 들어 이해

단어 = {“may”,“student”,“students”,“dog”,”studentssess”,“god”,“cat”,“act”,”tab”,“bat”,“flow”,“wolf” , "양고기", "아미", "얌", "밤", "반복", "푸들"}

해시 테이블은 다음과 같습니다.

동일한 문자 집합을 가진 그룹 단어

동일한 문자 집합을 사용하는 그룹 단어 구현

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).

공간 복잡성

해시 테이블을 유지하고 있으므로 공간 복잡성은 의 위에).

참조

Translate »