Group Anagrams

An anagram is produced by rearranging the letters of first String into another String. Therefore, if String t is an anagram of String s, sorting both strings will result in two identical strings. Furthermore, if s and t have different lengths, t must not be an anagram of s and we can return early. Consider the following examples of anagram set:

act, cat
tab, bat
tar, rat
star,rats

The following method can be used to check if two Strings are an anagram or not.

public boolean isAnagram(String s, String t) {
  if (s.length() != t.length()) {
    return false;
  }
  char[] str1 = s.toCharArray();
  char[] str2 = t.toCharArray();
  Arrays.sort(str1);
  Arrays.sort(str2);
  return Arrays.equals(str1, str2);
}

Complexity analysis:

Time Complexity:  Ο(nlogn). Assume that n is the length of s, sorting costs Ο(nlogn) and comparing two strings costs O(n). Sorting time dominates and the overall time complexity is O(nlogn).

Space Complexity: O(1). Space depends on the sorting implementation which, usually, costs O(1) auxiliary space if heapsort is used. Note that in Java, toCharArray() makes a copy of the string so it costs O(n) extra space, but we ignore this for complexity analysis as it is language-specific.

Now Given a set of random Strings, We need to write a function that groups all the anagrams together. This is an extension of identifying the anagrams. We can use HashMap to store the anagram group together. The algorithm is based on the logic: “sorting all anagrams will result in an identical String”. So, the key is the sorted word and the value is a list of words which sorts to an identical String. We will use the following data structure to store the anagram set:

Map<String,List> anagramGroup = new HashMap<>();

Where the key is the sorted result of a word and the value is the list of all anagrams.

  1. Iterate over the List/ Array of words.
  2. For each word convert the word into a character array. So if the word is “cat” then the array will be [c,a,t].
  3. Sort the array using Arrays.sort(char[]), so here the resulting sorted array will be [a,c,t].
  4. Again convert the array to String and check if there is any entry present for this key “act”.
  5. If entry is present then add the original word “cat” in the List present in the value field.
  6. Else create a new list and add the original word “cat” in the list and place the list in value filed against the sorted key.
  7. Now if the word “act”/”tac” comes. Then the sorted key will be “act”. And we will find an entry for the key “act” and add both the word in the list.

Now let us check the Java implementation for the same:

import java.util.*;

public class AnagramSet {

    public static void main(String[] args) {
        String[] StrArr = {"star", "dog", "car", "rats", "ars", "rca"};
        List<List<String>>  anagramGroup= getAnagramSet(StrArr);
        System.out.println(anagramGroup);
    }

    public static List<List<String>> getAnagramSet(String[] arr) {
        List<List<String>> anagramGroup = new ArrayList<>();
        if (arr == null || arr.length == 1) {
            return anagramGroup;
        }
        Map<String, List<String>> anagramMap = new HashMap<>();
        for (String word : arr) {
            char[] charArray = word.toCharArray();
            Arrays.sort(charArray);
            String sorted = String.copyValueOf(charArray);
            List<String> wordList = anagramMap.get(sorted);
            if (wordList == null) {
                wordList = new ArrayList<>();
                wordList.add(word);
                anagramMap.put(sorted, wordList);
            } else {
                anagramMap.get(sorted).add(word);
            }
        }
        return new ArrayList(anagramMap.values());
    }
}

Complexity Analysis

  • Time Complexity: O(NKlogK), where N is the length of arr[], and K is the maximum length of a string in arr. The outer loop has complexity O(N) as we iterate through each string. Then, we sort each string in O(KlogK) time.
  • Space Complexity: O(NK), the total information content stored in arr

Categories: String

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s