package com.zerroi.leetcode.Three19;

import java.util.*;

public class GroupAnagrams {
	public static void main(String[] args) {
        SolutionSecond solutionSecond = new SolutionSecond();
        List<List<String>> res = solutionSecond.groupAnagrams(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"});
        res.forEach(System.out::println);
    }
}

class SolutionSecond {
    public List<List<String>> groupAnagrams(String[] strs) {
    	if (strs.length <= 1) Arrays.asList(strs);

        List<List<String>> res = new ArrayList<>();
        List<String> path = new ArrayList<>();
        boolean[] walked = new boolean[strs.length];
        for (int i = 0; i < strs.length; i++) {
            if (walked[i]) continue;
            path.add(strs[i]);
            for (int j = i + 1; j < strs.length; j++) {
                if (isAnagram(strs[i], strs[j])) {
                    path.add(strs[j]);
                    walked[j] = true;
                }
            }
            res.add(new ArrayList<>(path));
            path.clear();
        }
        return res;
    }

    private boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        int[] count = new int[26];
        for (char c : s.toCharArray()) {
            count[c - 'a']++;
        }
        for (char c : t.toCharArray()) {
            count[c - 'a']--;
            if (count[c - 'a'] < 0) return false;
        }
        return true;
    }

    public List<List<String>> groupAnagrams(String[] strs, int a) {
        Map<String, List<String>> map = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            char[] array = strs[i].toCharArray();
            Arrays.sort(array);
            String str = new String(array);
            List<String> list = map.getOrDefault(str, new ArrayList<>());
            list.add(strs[i]);
            map.put(str, list);
        }
        return new ArrayList<>(map.values());
    }
}