49. Group Anagrams

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> group = new HashMap<>();
        for (String s : strs) {
            char[] cAry = s.toCharArray();
            Arrays.sort(cAry);
            String sortedKey = String.valueOf(cAry);
            group.computeIfAbsent(sortedKey, k -> new ArrayList<>()).add(s);
        }
        List<List<String>> result = new ArrayList<>();
        result.addAll(group.values());
        return result;
    }
}

/**
O(n*wlogw)
O(n*w) 
 */

https://leetcode.com/problems/group-anagrams/

1. O(n*wlogw),

2. O(n*w)

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // sort str
        // store in HashMap
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            
            // char ca[] = s.toCharArray();  //1
            // Arrays.sort(ca);
            
            char ca[] = new char[26]; //2
            for (char c : s.toCharArray()) {
                ca[c - 'a']++;
            }
            
            String keyStr = String.valueOf(ca);
            
            if (!map.containsKey(keyStr)) {
                map.put(keyStr, new ArrayList<String>());
            }
            map.get(keyStr).add(s);

        }
        
        return new ArrayList<>(map.values());
    }
}

easier one

O(n*w), n is strs[] length, w is word length

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            String encodedStr = encoding(s);
            map.putIfAbsent(encodedStr, new ArrayList<>());
            map.get(encodedStr).add(s);
        }
        return new ArrayList<>(map.values()); // in this way is easier
    }
    private String encoding(String s) {
        char[] ch = new char[26];
        for (char c : s.toCharArray()) {
            ch[c - 'a']++;
        }
        return new String(ch);
    }
}

/*
eat
tea
ate

how to ensure they're the same word?
use alpabet sort
so eat, tea, ate becomes -> aet

but sort is wlogw
total: O(nwlogw)

any other better?
use count sort

encoding: O(w)
char[26] -> to cal the count
at last new String(char)



*/