Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

public ArrayList<String> anagrams(String[] strs) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<String> output = new ArrayList<String>();
        HashMap<String,ArrayList<String>> patterns = new HashMap<String,ArrayList<String>>();

        for(int i=0;i<strs.length;i++){
            char[] charArr = strs[i].toCharArray();
            Arrays.sort(charArr);
            String sorted = new String(charArr);

            if(patterns.containsKey(sorted)){
                patterns.get(sorted).add(strs[i]);
            }else{
                ArrayList<String> newPattern = new ArrayList<String>();
                newPattern.add(strs[i]);
                patterns.put(sorted,newPattern);
            }
        }

        for(String str :patterns.keySet()){
            if(patterns.get(str).size()>1){
                output.addAll(patterns.get(str));
            }
        }
        return output;
    }

Analysis: Time complexity: O(n*mlgm)  (n is # of strings, m is the average length of each string) Space Complexity: O(n*m)

Share