A simple JAVA solution ~27 ms


  • 0
    A

    The basic logic is listed in the code comments below.
    The core method is "getSignature" .

    Time complexity analysis
    If number of strings is N, and assume that the longest string is of length K.
    Computing signature of each string takes O(K + 26) time.
    Total time for signature computation = O(KN + 26N).

    Total time for putting strings in hashMap = O(KN + 26N) + O(KN) = O(KN + 26N).

    Time for generating desired list = O(KN + 26N).

    Overall time complexity = O(KN + 26N).
    Overall space complexity = size of hashMap + size of auxiliary table for computing signature = O(NK) + O(26N) = O(KN + 26N).

    import java.util.*;
    
    public class Solution 
    {
    public List<List<String>> groupAnagrams(String[] strs) 
    	{
    		List<List<String>> list = new ArrayList<List<String>>();
            if(strs != null)
            {
            	HashMap<String, ArrayList<String>> groups = new HashMap<String, ArrayList<String>>();
            	int N = strs.length;
            	String string, sign;
            	int i;
            	ArrayList<String> set = new ArrayList<String>();
            	
            	for(i = 0; i < N; i++)
            	{
            		string = strs[i];
            		sign = getSignature(string);
            		set = groups.getOrDefault(sign, new ArrayList<String>());
                    
                    // this logic ensures that relative order is retained
            		set.add(string);
            		groups.put(sign, set);
            	}
            	
            	for(String key : groups.keySet())
            	{
            		list.add(groups.get(key));
            	}
            }
            
            return list;
        }
    	
        // Computes "signature" of a string
        // A signature is simply a concatenation of characters (present in string) in alphabetical order
        // e.g. Consider the string "anagram"
        // It has character counts as a = 3, g = 1, m = 1, n = 1, r = 1.
        // So, its signature is "aaagmnr"
    	private String getSignature(String string)
    	{
    		int[] counts = new int[26];
    		Arrays.fill(counts, 0);
    		int N = string.length();
    		int i, j;
    		char currentCharacter;
    		
            // count occurences of each alphabet
    		for(i = 0; i < N; i++)
    		{
    			currentCharacter = string.charAt(i);
    			++counts[currentCharacter - 'a'];
    		}
    		
    		// construct the signature
    		StringBuilder signature = new StringBuilder();
    		for(i = 0; i < 26; i++)
    		{
    			currentCharacter = (char)(97 + i);
    			for(j = 0; j < counts[i]; j++)
    			{
    				signature.append(currentCharacter);
    			}
    		}
    		
    		return signature.toString();
    	}    	
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.