package com.freetymekiyan.algorithms.level.medium;

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

/**
 * Given an array of strings, group anagrams together.
 * <p>
 * For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
 * Return:
 * <p>
 * | [
 * |   ["ate", "eat","tea"],
 * |   ["nat","tan"],
 * |   ["bat"]
 * | ]
 * Note: All inputs will be in lower-case.
 * <p>
 * Company Tags: Amazon, Bloomberg, Uber, Facebook, Yelp
 * Tags: Hash Table, String
 * Similar Problems: (E) Valid Anagram, (E) Group Shifted Strings
 */
public class GroupAnagrams {

    /**
     * Hash Table.
     * Use sorted word as the key, since all anagrams share the same sorted form.
     * Then same anagrams form a list as the value.
     * For each word, sort its character array and build a string key.
     * If the key is not in map yet, add an empty array list to map.
     * Then add the word to the list.
     * <p>
     * A possible improvement is sorting the word using counting sort. Two pass.
     * Since all inputs are lowercase characters.
     * Reduce sorting time from O(nlogn) to O(n).
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) {
            return Collections.emptyList();
        }
        Map<String, List<String>> map = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            char[] word = strs[i].toCharArray();
            Arrays.sort(word);
            String key = String.valueOf(word);
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }
            map.get(key).add(strs[i]);
        }
        return new ArrayList<>(map.values());
    }
}

@@ -66,149 +66,44 @@
 til.
-ArrayList;%0Aimport java.util.Arrays;%0Aimport java.util.Collections;%0Aimport java.util.HashMap;%0Aimport java.util.List;%0Aimport java.util.Map;%0A%0A/**
+*;%0A%0A/**%0A * 49. Group Anagrams%0A * %3Cp%3E
 %0A * 
@@ -1297,19 +1297,22 @@
 tring%3E%3E 
-map
+groups
  = new H
@@ -1340,123 +1340,71 @@
 or (
-int i = 0; i %3C strs.length; i++) %7B%0A            char%5B%5D word = strs%5Bi%5D.toCharArray();%0A            Arrays.sort(word
+String s : strs) %7B%0A            String key = getSortedKey(s
 );%0A
+//
     
@@ -1428,27 +1428,19 @@
 y = 
-String.valueOf(word
+getMapKey(s
 );%0A 
@@ -1455,19 +1455,22 @@
    if (!
-map
+groups
 .contain
@@ -1498,19 +1498,22 @@
         
-map
+groups
 .put(key
@@ -1560,19 +1560,22 @@
         
-map
+groups
 .get(key
@@ -1585,14 +1585,8 @@
 dd(s
-trs%5Bi%5D
 );%0A 
@@ -1629,20 +1629,525 @@
 t%3C%3E(
-map.values()
+groups.values());%0A    %7D%0A%0A    private String getSortedKey(String word) %7B%0A        char%5B%5D chars = word.toCharArray();%0A        Arrays.sort(chars);%0A        return String.valueOf(chars);%0A    %7D%0A%0A    private String getMapKey(String word) %7B%0A        int%5B%5D counts = new int%5B26%5D; // 26 lowercase letters.%0A        for (char c : word.toCharArray()) %7B%0A            counts%5Bc%5D++;%0A        %7D%0A        StringBuilder key = new StringBuilder();%0A        for (int n : counts) %7B%0A            key.append(n);%0A        %7D%0A        return key.toString(
 );%0A 
@@ -2152,9 +2152,8 @@
 %0A    %7D%0A%7D
-%0A

update 49. Group Anagrams