Group Anagrams - LeetCode Solution and Approach

  

 49. Group Anagrams - LeetCode - Medium

Solve this problem in LeetCode

Problem Description:

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]

Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

Input: strs = [""]

Output: [[""]]

Example 3:

Input: strs = ["a"]

Output: [["a"]]

Constraints:

1 <= strs.length <= 104

0 <= strs[i].length <= 100

strs[i] consists of lowercase English letters.

Approach:

We need to place same anagrams in groups.

We can sort the elements in array and easily check for similar anagrams. But we will use another approach that is slightly more efficient.

Rather than sorting each string, we can calculate frequency of each character and store in variable say freq. We can now easily form a string of freq and hence it will be same for same frequency of characters. We can now make groups based on string frequency.

• We will iterate through given string array.
• We will count the character frequency of current string and store in variable say freq.
• We will convert value of freq variable to String to act as key. This key will be same when a string has same number of characters.
• We will add the current string in the group based on key. And keep on iterating.
• After iterating, we will get the groups of anagrams in values of Map.

JAVA:

Time Complexity : 0(nk), where n is number of strings, and k is length of each string

Space Complexity: 0(n)

class Solution {

    public List <List<String >> groupAnagrams(String[] strs) {
        if (strs.length == 0 || strs == null) return new ArrayList <>();

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

        for (String str: strs) {
            char[] freq = new char[26];
            for (char ch: str.toCharArray()) freq[ch - 'a']++; // calculating frequency

            String key = String.valueOf(freq); // converting freq to string to act as key
            map.computeIfAbsent(key, k->new ArrayList<>()).add(str); // adding string to its group based on key
        }
        return new ArrayList<>(map.values());
    }
}

Keep Learning and Practicing with Programming Chaska !!!