My Accepted Java solution. Is there any way to improve time Complexity?


  • 0
    H
    public List<String> anagrams(String[] strs) {
        HashMap<String,List<String>> map = new HashMap<String,List<String>>();
        List<String> result = new ArrayList<String>();
        for(String s:strs)
        { 
            String s1 = sort(s);
            if(!map.containsKey(s1))
            {
            List<String> l = new ArrayList<String>();
            l.add(s);
            map.put(s1,l);
            }
            else
            {
                map.get(s1).add(s);
            }
        }
        for(String s:map.keySet())
        {
            if(map.get(s).size()>1)
            {
            result.addAll(map.get(s));
            }
        }
        return result;
    }
    public String sort(String s)
    {
      char[] c= s.toCharArray();
      Arrays.sort(c);
      return new String(c);
    }

  • 0
    J

    Here are some of my ideas:

    • (minor idea) You can if fact eliminate the second loop and populate the result as you go.
    • (major idea) use counting sort for the characters instead of general purpose QuickSort/MergeSort, this would end up with O(N M R) instead of O(N lg M) where: N - the array size, M - the length of words, R the alphabet size

Log in to reply
 

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