Group Anagrams LeetCode Solution

Problem Statement

Group Anagrams LeetCode Solution Says that – 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 <= 10⁴
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters.

ALGORITHM –

IDEA –

• In order to Find Group Anagrams. First, we will focus on the anagrams(after sorting the words are the same).
• So, first traversed through the array and sort each word in order to find anagrams.
• We will make one Hashmap and check if sorted words are present in Hashmap then we will append that non-sorted words into the list as value and key as sorted words.
• Else sorted word as key and value as non-sorted word as a value within a list.
• and At last we will create one answer list and  will run a loop in hash map and add the values in answer.
• Hence We will find the Group Anagrams.

Approach –

• At first we will create one Hashmap and a list that will return the answer.
• After that will run a loop from 0 to length of array and sort each words.
• after sorting each words we will check if it is present in hashmap or not if it is present then will the non-sorted word into the value else will create one non-sorted word list as value and key as sorted word.
• At last we will traverse the whole Hashmap and append value into ans and return ans.
• Hence we will Find the Group Anagrams.

Image of the solution –

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        
        ans = []
        dic = {}
        for i in range(len(strs)):
            k = ""
            for j in sorted(strs[i]):
                k += j
                
            if k in dic:
                dic[k].append(strs[i])
            
            else:
                dic[k] = [strs[i]]
                
                
        for i in dic:
            ans.append(dic[i])

        return ans

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
      List<List<String>> ans = new ArrayList<>();
        HashMap<String, List<String>> dic = new HashMap<>();
    
        
        for (int i = 0; i < strs.length; i++) {
    	    String temp = strs[i];
    	    char[] ch = temp.toCharArray();
    	    Arrays.sort(ch);
    	    if (dic.containsKey(String.valueOf(ch))) {
    		    dic.get(String.valueOf(ch)).add(strs[i]);
    	    } else {
    		    List<String> each = new ArrayList<>();
    		    each.add(strs[i]);
    		    dic.put(String.valueOf(ch), each);
    	    }
        }
        for (List<String> item: dic.values()) {
    	    ans.add(item);
        }
        return ans;
    }
    

}

TIME COMPLEXITY : O(N*K(LOGK)), K = Len(Words).

SPACE COMPLEXITY: O(N), As we have taken Extra Space.

SIMILAR QUESTIONS – https://tutorialcup.com/leetcode-solutions/minimum-number-of-steps-to-make-two-strings-anagram-leetcode-solutions.htm