O(n) time complexity. n equals to number of characters in all strings. (No sort)


  • 1
    C

    The idea of this solution is to convert all anagrams to one same string. I count all characters in a string and convert it. For example: abbccaaa will be converted to 4a2b2c. In this case, all anagrams will be converted to the same string.

    Like it if you like my solution!

    public List<List<String>> groupAnagrams(String[] strs) {
         List<List<String>> result=new ArrayList<List<String>>();
         HashMap<String,Integer> pos=new HashMap<String,Integer>();
         String temp;
         for(int i=0;i<strs.length;i++){
             temp=parse(strs[i]);
             if(pos.containsKey(temp)){
                 List<String> anagram=result.get(pos.get(temp));
                 anagram.add(strs[i]);
             }else{
                 List<String> newEntry=new ArrayList<String>();
                 newEntry.add(strs[i]);
                 result.add(newEntry);
                 pos.put(temp,result.size()-1);
             }
         }
         return result;
    }
    
    public String parse(String str){
        int[] count=new int[26];
        char temp;
        String result="";
        for(int i=0;i<str.length();i++){
            temp=str.charAt(i);
            count[temp-'a']++;
        }
        for(int i=0;i<26;i++) {
            temp=(char)('a'+i);
            result=result+count[i]+temp;
        }
        return result;
    }

  • 0
    G

    It is not necessary to build the key by parsing abbccaaa into 4a2b2c, List<Integer> can be used as key for Map. Please refer to this solution.


Log in to reply
 

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