Group words with same set of characters in Java

In this tutorial you are going to learn, how to Group Words with Same Set of Characters in Java with some examples. In many situations, either directly or indirectly we might have to come up with these types of problems.

Here a list of words is passed as an input, and we will be implementing a method to identify all words that have the same set of characters. And the output we are expecting over here is, to get all possible words with same set of characters to be displayed together.

Example:

Input:
words[] = {“not”, “ton”,“now”, “dog”, “won”,
“no”, “bat”, “tab”, “but”, “tub”,
“god”, “on”};

Output:
no, on,
not, ton,
bat, tab,
but, tub,
now, won,
dog, god

The strategy here is to make use of hashing. We will be generating a key for all the given words. The key contains all unique character, as the name ‘key’ itself indicates uniqueness. And which we will be storing all the distinct characters of the string in a sorted way. Later we will use hashing strategy to all the words with same key. Finally once we completed all keys and values in the hash table, we will be printing the result by traversing the same hash table. Hence we will be achieving all possible words with same set of characters in java has the output.

Java program to group words with the same set of characters

By implementing the above method, we can construct our code as follow,

// Java program to print all words that have the same unique character set 
import java.util.HashMap; 
import java.util.Map.Entry; 
import java.util.ArrayList; 
import java.util.Arrays; 

public class SameSet { 

  static final int MAX_CHAR = 26; 
  
  // The below function generates a key from given string. The key contains all unique characters of given string 
  // in sorted order consisting of only distinct elements. 
  static String getKey(String str) 
  { 
    boolean[] visited = new boolean[MAX_CHAR]; 
    Arrays.fill(visited, false); 
  
    // Store all unique characters of current word in key 
    for (int j = 0; j < str.length(); j++) 
      visited[str.charAt(j) - 'a'] = true ; 
    String key = ""; 
    for (int j=0; j < MAX_CHAR; j++) 
      if (visited[j]) 
        key = key + (char)('a'+j); 
    return key; 
  } 
  
  // Print all words together with same character sets. 
  static void wordsWithSameChar(String w[], int n) 
  { 

    HashMap<String, ArrayList<Integer>> h = new HashMap<>(); 
  
    for (int i=0; i<n; i++) 
    { 
      String key = getKey(w[i]); 
      
      // If the key is already in the map then get its corresponding value and update the list and put it in the map 
      if(h.containsKey(key)) 
      { 
        ArrayList<Integer> al = h.get(key); 
        al.add(i); 
        h.put(key, al); 
      } 
      
      // If key is not present in the map then create a new list and add both key and update the list 
      else
      { 
        ArrayList<Integer> al = new ArrayList<>(); 
        al.add(i); 
        h.put(key, al); 
      } 
    } 
  
    // Print's all words that have the same unique character set
    System.out.println("All words that have the same unique character set are: ");		
    for (Entry<String, ArrayList<Integer>> it : h.entrySet()) 
    { 
      ArrayList<Integer> get =it.getValue(); 
      for (Integer v:get)
        System.out.print( w[v] + ", "); 
      System.out.println(); 
    } 
  } 
  public static void main(String args[]) 
  { 
    String w[] = {"not", "ton","now", "dog", "won",
          "no", "bat", "tab", "but", "tub",
          "god", "on"};

    int n = w.length; 
    wordsWithSameChar(w, n); 
  } 
}

Output:

All words that have the same unique character set are: 
no, on, 
not, ton, 
bat, tab, 
but, tub, 
now, won, 
dog, god

Time complexity: O (n*k) where n is number of words in the dictionary and k is max length of the given word.

Leave a Reply

Your email address will not be published. Required fields are marked *