Group Anagrams LeetCode Solution


Frequently asked in Adobe Amazon American Express Apple BlackRock Bloomberg ByteDance Citadel DE Shaw Expedia Google Intel Mathworks Microsoft Morgan Stanley Netflix Nvidia Oracle PayPal ServiceNow Twitter Two Sigma VMware Yelp
categories - MediumViews 6721

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 <= 104
  • 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 –

Group Anagrams LeetCode Solution

Group Anagrams LeetCode Solution

Group Anagrams LeetCode 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

 

Translate »