In Group words with same set of characters problem, we have given a list of words with lower cases. Implement a function to find all Words that have the same unique character set.
Table of Contents
Example
Input
Words[]={ “may”, “student”, “students”, “dog”,”studentssess”, “god”, “cat”, “act”,”tab”, “bat”, “flow”, “wolf”, “lambs”,”amy”, “yam”, “balms”, “looped”, “poodle”}
Output
may, amy, yam,
student, students, studentssess,
dog, god,
cat, act,
tab, bat,
flow, wolf,
lambs, balms,
looped, poodle
Approach 1: Brute force
Main idea
For each word, we will iterate over all the words and find those words with the same set of characters and then print it.
The words we have already printed, we will mark them so that we will not print them again.
Algorithm for Group Words With Same Set of Characters
- Run a loop for I in range 0 to n-1
- If the length of the words[i] is equal, then skip it because we have already printed it.
- Make an array charSet1 which will store the characters which are present in words[i].
- Run a loop for j in the range I to n-1
- Make an array charSet2 which will store the characters which are present in words[j]
- If charSet1 is equal to charSet2, then print words[j] and change words[j] to an empty string which denotes that we have printed this string.
- Return
Implementation for Group Words With Same Set of Characters
C++ program
#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 program
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,
Complexity Analysis
Time complexity
We are using three nested loops, two of them have size N, and the third one has a size of the length of strings. If we take lengths of string to be L, then the total time complexity is O(N*N*L).
Space complexity
We are not using any extra space so the space complexity is O(1).
Approach 2: Using Hashing
Main idea
We will make a key for every string which will store all the distinct characters of the string in a sorted manner. After that, we will use hashing to all the words with the same key and will print them in the end.
Algorithm for Group Words With Same Set of Characters
- Declare a hash_table which will store all index of all the words having the same key.
- Make a function makeKey, which will return the key for a string.
- Run a loop for I in range 0 to n-1
- Insert I in the hash_table for the key of ‘words[i]’.
- Iterate over the hash table and print the strings with the same key.
- Return
Understand with example
Words = { “may”, “student”, “students”, “dog”,”studentssess”, “god”, “cat”, “act”,”tab”, “bat”, “flow”, “wolf”, “lambs”,”amy”, “yam”, “balms”, “looped”, “poodle”}
The hash table will look like this:
Implementation for Group Words With Same Set of Characters
C++ program
#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 program
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,
Complexity Analysis
Time complexity
We are iterating over the array only once and in each iteration, we are generating a key by iterating over the string. So, if we take the length of the string be L, then the total time complexity is O(N*L).
Space Complexity
We are maintaining a hash table, so the space complexity is O(N).