Untitled

class TrieNode {
    TrieNode[] children;
    List<String> words;

    TrieNode() {
        children = new TrieNode[26]; 
        words = new ArrayList<>(); 
    }
}

class Solution {
    public void insert(TrieNode root, String original, String sortedStr) {
        TrieNode current = root;

        
        for (char ch : sortedStr.toCharArray())  
        {
            int index = ch - 'a';
            if (current.children[index] == null) 
            current.children[index] = new TrieNode();
            
            current = current.children[index];
        }
        
        current.words.add(original);
    }

    public void dfs(TrieNode node, List<List<String>> result) {
        
        if (node.words.isEmpty()==false) {
            result.add(node.words);
        }

       
        for (int i = 0; i < 26; i++) {
            if (node.children[i] != null) {
                dfs(node.children[i], result);
            }
        }
    }

    public List<List<String>> groupAnagrams(String[] strs) {
        TrieNode root = new TrieNode();

        // O(N* (llog(l)+O(l))) => O(N*Llog(l) + O(N*L)) => O(N*Llog(l)
        for (String str : strs)   // O(n)
        { 
            char[] chars = str.toCharArray();
            Arrays.sort(chars);               // O(Llog(l))
            String sortedStr = new String(chars);
            insert(root, str, sortedStr);  // O(L)
        }

       
        List<List<String>> result = new ArrayList<>();
        //O()
        dfs(root, result);

        return result;
    }
}