Tips for Java user


  • 3
    K

    I use Hashtable first,
    got TLE.

    Then tried HashMap,
    AC.

    Oh, man.


  • 2
    D

    Woooo Hoooo!!!
    That helps a lot!
    Thank you ! ! !! !
    Saved my ass... !!!


  • 0
    F

    I have implemented using sorting and Hashtable. The strs array is scanned once, and each string is sorted. This is used as the key to the hash table, whereas the index of the original string is added as the value. If several strings have same sorted result, they are saved as collection of indexes (ArrayList). At the end, any hash element that has ArrayList with size larger than 1, can be treated as a group of anagrams.

    Time complexity for sorting each string is O(n) (n being length of string), and space complexity O(26) (since all strings are lower case). Total time complexity O(n*w) (n-number of strings in array, w - avg length of each string).

    Additional time/space complexity O(u) (u being number of elements in hash table). Size of Hashtable depends on number of unique anagrams. Below is the code.

    public class Solution {
        String sort(String s)
    	{
    		char []freq = new char[26];
    		for (int i=0; i<s.length(); i++)
    		{
    			int ind = (int)(s.charAt(i) - 97);
    			if (ind>=0 && ind <=26)
    				freq[ind]++;
    		}
    		String sorted = "";
    		for (int i=0; i<26; i++)
    		{
    			for (int j=0; j<freq[i]; j++)
    			{
    				char c = (char)(97+i);
    				sorted += c;
    			}
    		}
    	 return sorted;
    	}
        public ArrayList<String> anagrams(String[] strs)
        {
    		ArrayList<String> an = new ArrayList<String>();
            Hashtable<String, ArrayList<Integer>> hash = new Hashtable<String, ArrayList<Integer>>();
            
            for (int i=0; i<strs.length; i++)
            {
            	String curr = sort(strs[i]);
            	ArrayList<Integer> list = hash.get(curr);
            	if (list == null)
            		list = new ArrayList<Integer>();
            	list.add(i);
            	hash.put(curr, list);
            }
            for (String key : hash.keySet())
            {
            	ArrayList<Integer> list = hash.get(key);
            	if (list.size()>1)
            	{
            		for (int i=0; i<list.size(); i++)
            			an.add(strs[list.get(i)]);
            	}
            }
    
         return an;
        }
    }

  • 0
    D


    private String getMapKey(String s) {
    char[] c = s.trim().toCharArray();
    Arrays.sort(c);
    return new String(c);
    }

    Also you can use the values() method of hashmap or hashtable.


  • 0
    B

    Hashtable is thread safety. There is a lot of synchronized methods in the source code. It's generally slower than HashMap in OJ problems.


  • 0
    B

    Also, when list.size() > 1 , an.addAll(list) can be used instead of a for loop to add element.


Log in to reply
 

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