Группировка анаграмм

JavaScript

class Solution {
    // Using sorted string as key
    groupAnagrams(strs) {
        const groups = {};
        
        for (const str of strs) {
            const sorted = str.split('').sort().join('');
            if (!groups[sorted]) groups[sorted] = [];
            groups[sorted].push(str);
        }
        
        return Object.values(groups);
    }
    // Time: O(n * k * log(k)), Space: O(n * k)
    // где n - количество строк, k - максимальная длина строки

    // Using character count as key
    groupAnagramsCount(strs) {
        const groups = new Map();
        
        for (const str of strs) {
            const count = new Array(26).fill(0);
            for (const char of str) {
                count[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
            }
            const key = count.join('#');
            if (!groups.has(key)) groups.set(key, []);
            groups.get(key).push(str);
        }
        
        return Array.from(groups.values());
    }
    // Time: O(n * k), Space: O(n * k)
}

Java

class Solution {
    // Using sorted string as key
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String sorted = new String(chars);
            
            groups.computeIfAbsent(sorted, k -> new ArrayList<>()).add(str);
        }
        
        return new ArrayList<>(groups.values());
    }
    // Time: O(n * k * log(k)), Space: O(n * k)

    // Using character count as key
    public List<List<String>> groupAnagramsCount(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        
        for (String str : strs) {
            int[] count = new int[26];
            for (char c : str.toCharArray()) {
                count[c - 'a']++;
            }
            
            StringBuilder key = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                key.append('#').append(count[i]);
            }
            
            groups.computeIfAbsent(key.toString(), k -> new ArrayList<>()).add(str);
        }
        
        return new ArrayList<>(groups.values());
    }
    // Time: O(n * k), Space: O(n * k)
}

Python

class Solution:
    # Using sorted string as key
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = collections.defaultdict(list)
        
        for s in strs:
            groups[''.join(sorted(s))].append(s)
            
        return list(groups.values())
    # Time: O(n * k * log(k)), Space: O(n * k)

    # Using character count as key
    def groupAnagrams_count(self, strs: List[str]) -> List[List[str]]:
        groups = collections.defaultdict(list)
        
        for s in strs:
            count = [0] * 26
            for c in s:
                count[ord(c) - ord('a')] += 1
            groups[tuple(count)].append(s)
            
        return list(groups.values())
    # Time: O(n * k), Space: O(n * k)

Для каждого языка представлены два решения:

1. С использованием сортировки символов как ключа (проще для понимания)
2. С использованием подсчета символов как ключа (оптимальнее по времени)