LeetCode - Group Anagrams - 30Days Challenge

Given an array of strings, group anagrams together.

Example:

Input: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”], Output: [ [“ate”,”eat”,”tea”], [“nat”,”tan”], [“bat”] ]

Note:

All inputs will be in lowercase.

The order of your output does not matter.

Solution

To group Anagram words, We can sort all string with characters and match it with other string to verify if its anagram or not. We can use Map to group all equal strings.

Code


import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Anagram {

	public static void main(String[] args) {
		String[] arr = { "eat", "tea", "tan", "ate", "nat", "bat" };
		System.out.println(new Anagram().groupAnagrams(arr));

	}

	public List<List<String>> groupAnagrams(String[] strs) {

		Map<String, List<String>> map = new HashMap<>();

		for (String str : strs) {

			char[] cArr = str.toCharArray();
			Arrays.sort(cArr);
			String key = new String(cArr);

			if (map.containsKey(key)) {
				List<String> list = map.get(key);
				list.add(str);
			} else {
				List<String> list = new ArrayList<>();
				list.add(str);
				map.put(key, list);
			}
		}

		List<List<String>> res = new ArrayList<>();

		for (String key : map.keySet()) {
			res.add(map.get(key));
		}

		return res;
	}

}