49. Group Anagrams

Description

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Constraints

• 1 <= strs.length <= 104

• 0 <= strs[i].length <= 100

• strs[i] consists of lowercase English letters.

Approach

Links

• Binarysearch

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

Output: [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]

Example 2

Input: strs = [""]

Output: [[""]]

Example 3

Input: strs = ["a"]

Output: [["a"]]

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        
        for(String s: strs) {
            int[] counter = new int[26];
            for(char ch: s.toCharArray()) {
                counter[ch - 'a']++;
            }
            
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < 26; i++) {
                sb.append("#").append(counter[i]);
            }
            
            String key = sb.toString();
            if(!map.containsKey(key)) {
                map.put(key, new ArrayList());
            }
            map.get(key).add(s);
        }
        
        return new ArrayList(map.values());
    }
}

Follow up