49. Group anagrams

49_solution1_pairwise_comparison.c

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

static bool isAnagram(const char *s, const char *t) {
  int freq[26] = {0};
  int lenS = strlen(s), lenT = strlen(t);
  if (lenS != lenT)
    return false;

  for (int i = 0; i < lenS; i++)
    freq[s[i] - 'a']++;
  for (int i = 0; i < lenT; i++) {
    freq[t[i] - 'a']--;
    if (freq[t[i] - 'a'] < 0)
      return false;
  }
  return true;
}

char ***groupAnagrams(char **strs, int strsSize, int *returnSize,
                       int **returnColumnSizes) {
  int *groupIndex = (int *)malloc(strsSize * sizeof(int));
  int *groupHead = (int *)malloc(strsSize * sizeof(int));
  int *groupCounts = (int *)calloc(strsSize, sizeof(int));
  int groupTotal = 0;

  for (int i = 0; i < strsSize; i++) {
    int found = -1;
    for (int g = 0; g < groupTotal; g++) {
      if (isAnagram(strs[i], strs[groupHead[g]])) {
        found = g;
        break;
      }
    }

    if (found == -1) {
      found = groupTotal;
      groupHead[groupTotal] = i;
      groupTotal++;
    }

    groupIndex[i] = found;
    groupCounts[found]++;
  }

  char ***result = (char ***)malloc(groupTotal * sizeof(char **));
  *returnColumnSizes = (int *)malloc(groupTotal * sizeof(int));
  int *filled = (int *)calloc(groupTotal, sizeof(int));

  for (int g = 0; g < groupTotal; g++) {
    result[g] = (char **)malloc(groupCounts[g] * sizeof(char *));
    (*returnColumnSizes)[g] = groupCounts[g];
  }

  for (int i = 0; i < strsSize; i++) {
    int g = groupIndex[i];
    result[g][filled[g]++] = strs[i];
  }

  free(groupIndex);
  free(groupHead);
  free(groupCounts);
  free(filled);

  *returnSize = groupTotal;
  return result;
}

49_solution2_sorting.c

#include <stdlib.h>
#include <string.h>

static int cmpChar(const void *a, const void *b) {
  return (*(char *)a - *(char *)b);
}

char ***groupAnagrams(char **strs, int strsSize, int *returnSize,
                       int **returnColumnSizes) {
  char **keys = (char **)malloc(strsSize * sizeof(char *));
  int *groupIndex = (int *)malloc(strsSize * sizeof(int));
  char **groupKeys = (char **)malloc(strsSize * sizeof(char *));
  int *groupCounts = (int *)calloc(strsSize, sizeof(int));
  int groupTotal = 0;

  for (int i = 0; i < strsSize; i++) {
    int len = strlen(strs[i]);
    keys[i] = (char *)malloc((len + 1) * sizeof(char));
    strcpy(keys[i], strs[i]);
    qsort(keys[i], len, sizeof(char), cmpChar);

    int found = -1;
    for (int g = 0; g < groupTotal; g++) {
      if (strcmp(keys[i], groupKeys[g]) == 0) {
        found = g;
        break;
      }
    }

    if (found == -1) {
      found = groupTotal;
      groupKeys[groupTotal] = keys[i];
      groupTotal++;
    }

    groupIndex[i] = found;
    groupCounts[found]++;
  }

  char ***result = (char ***)malloc(groupTotal * sizeof(char **));
  *returnColumnSizes = (int *)malloc(groupTotal * sizeof(int));
  int *filled = (int *)calloc(groupTotal, sizeof(int));

  for (int g = 0; g < groupTotal; g++) {
    result[g] = (char **)malloc(groupCounts[g] * sizeof(char *));
    (*returnColumnSizes)[g] = groupCounts[g];
  }

  for (int i = 0; i < strsSize; i++) {
    int g = groupIndex[i];
    result[g][filled[g]++] = strs[i];
  }

  for (int i = 0; i < strsSize; i++) {
    free(keys[i]);
  }
  free(keys);
  free(groupIndex);
  free(groupKeys);
  free(groupCounts);
  free(filled);

  *returnSize = groupTotal;
  return result;
}

49_solution3_frequency_serialization.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static void serializeFrequency(const char *s, char *key) {
  int alphabet[26] = {0};
  int len = strlen(s);

  for (int i = 0; i < len; i++)
    alphabet[s[i] - 'a']++;

  key[0] = '\0';
  char buf[12];
  for (int i = 0; i < 26; i++) {
    sprintf(buf, "%d#", alphabet[i]);
    strcat(key, buf);
  }
}

char ***groupAnagrams(char **strs, int strsSize, int *returnSize,
                       int **returnColumnSizes) {
  char **keys = (char **)malloc(strsSize * sizeof(char *));
  int *groupIndex = (int *)malloc(strsSize * sizeof(int));
  char **groupKeys = (char **)malloc(strsSize * sizeof(char *));
  int *groupCounts = (int *)calloc(strsSize, sizeof(int));
  int groupTotal = 0;

  for (int i = 0; i < strsSize; i++) {
    keys[i] = (char *)malloc(128 * sizeof(char));
    serializeFrequency(strs[i], keys[i]);

    int found = -1;
    for (int g = 0; g < groupTotal; g++) {
      if (strcmp(keys[i], groupKeys[g]) == 0) {
        found = g;
        break;
      }
    }

    if (found == -1) {
      found = groupTotal;
      groupKeys[groupTotal] = keys[i];
      groupTotal++;
    }

    groupIndex[i] = found;
    groupCounts[found]++;
  }

  char ***result = (char ***)malloc(groupTotal * sizeof(char **));
  *returnColumnSizes = (int *)malloc(groupTotal * sizeof(int));
  int *filled = (int *)calloc(groupTotal, sizeof(int));

  for (int g = 0; g < groupTotal; g++) {
    result[g] = (char **)malloc(groupCounts[g] * sizeof(char *));
    (*returnColumnSizes)[g] = groupCounts[g];
  }

  for (int i = 0; i < strsSize; i++) {
    int g = groupIndex[i];
    result[g][filled[g]++] = strs[i];
  }

  for (int i = 0; i < strsSize; i++) {
    free(keys[i]);
  }
  free(keys);
  free(groupIndex);
  free(groupKeys);
  free(groupCounts);
  free(filled);

  *returnSize = groupTotal;
  return result;
}

49_solution1_pairwise_comparison.cpp

#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
  vector<vector<string>> groupAnagrams(vector<string> &strs) {
    vector<vector<string>> result;

    for (string &s : strs) {
      bool placed = false;
      for (vector<string> &group : result) {
        if (isAnagram(s, group[0])) {
          group.push_back(s);
          placed = true;
          break;
        }
      }

      if (!placed) {
        result.push_back({s});
      }
    }
    return result;
  }

  bool isAnagram(string s, string t) {
    if (s.size() != t.size())
      return false;
    unordered_map<char, int> freq;
    for (char c : s)
      freq[c]++;
    for (char c : t) {
      if (--freq[c] < 0)
        return false;
    }
    return true;
  }
};

49_solution2_sorting.cpp

#include <algorithm>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
  vector<vector<string>> groupAnagrams(vector<string> &strs) {
    unordered_map<string, vector<string>> groups;

    for (string &s : strs) {
      string key = s;
      sort(key.begin(), key.end());
      groups[key].push_back(s);
    }

    vector<vector<string>> result;
    for (auto &it : groups) {
      result.push_back(it.second);
    }
    return result;
  }
};

49_solution3_frequency_serialization.cpp

#include <array>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
  vector<vector<string>> groupAnagrams(vector<string> &strs) {
    string key;
    vector<vector<string>> result;
    unordered_map<string, vector<string>> groups;

    for (string s : strs) {
      key = serializeFrequency(s);
      groups[key].push_back(s);
    }

    for (auto &it : groups) {
      result.push_back(it.second);
    }

    return result;
  }

  string serializeFrequency(string s) {
    array<int, 26> alphabet = {};
    string key = "";

    for (char c : s)
      alphabet[c - 'a']++;

    for (int i = 0; i < 26; i++)
      key += to_string(alphabet[i]) + "#";
    return key;
  }
};

49_solution1_pairwise_comparison.go

package main

func groupAnagrams(strs []string) [][]string {
    result := [][]string{}

    for _, s := range strs {
        placed := false
        for i, group := range result {
            if isAnagram(s, group[0]) {
                result[i] = append(group, s)
                placed = true
                break
            }
        }

        if !placed {
            result = append(result, []string{s})
        }
    }

    return result
}

func isAnagram(s, t string) bool {
    if len(s) != len(t) {
        return false
    }

    freq := make(map[rune]int)
    for _, c := range s {
        freq[c]++
    }
    for _, c := range t {
        freq[c]--
        if freq[c] < 0 {
            return false
        }
    }
    return true
}

49_solution2_sorting.go

package main

import "sort"

func groupAnagrams(strs []string) [][]string {
    groups := make(map[string][]string)

    for _, s := range strs {
        chars := []byte(s)
        sort.Slice(chars, func(i, j int) bool { return chars[i] < chars[j] })
        key := string(chars)
        groups[key] = append(groups[key], s)
    }

    result := make([][]string, 0, len(groups))
    for _, group := range groups {
        result = append(result, group)
    }
    return result
}

49_solution3_frequency_serialization.go

package main

import (
    "strconv"
    "strings"
)

func groupAnagrams(strs []string) [][]string {
    groups := make(map[string][]string)

    for _, s := range strs {
        key := serializeFrequency(s)
        groups[key] = append(groups[key], s)
    }

    result := make([][]string, 0, len(groups))
    for _, group := range groups {
        result = append(result, group)
    }
    return result
}

func serializeFrequency(s string) string {
    var alphabet [26]int
    for _, c := range s {
        alphabet[c-'a']++
    }

    var key strings.Builder
    for i := 0; i < 26; i++ {
        key.WriteString(strconv.Itoa(alphabet[i]))
        key.WriteByte('#')
    }
    return key.String()
}

49_solution1_pairwise_comparison.java

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

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> result = new ArrayList<>();

        for (String s : strs) {
            boolean placed = false;
            for (List<String> group : result) {
                if (isAnagram(s, group.get(0))) {
                    group.add(s);
                    placed = true;
                    break;
                }
            }

            if (!placed) {
                List<String> group = new ArrayList<>();
                group.add(s);
                result.add(group);
            }
        }

        return result;
    }

    private boolean isAnagram(String s, String t) {
        if (s.length() != t.length())
            return false;

        Map<Character, Integer> freq = new HashMap<>();
        for (char c : s.toCharArray())
            freq.merge(c, 1, Integer::sum);
        for (char c : t.toCharArray()) {
            int count = freq.merge(c, -1, Integer::sum);
            if (count < 0)
                return false;
        }
        return true;
    }
}

49_solution2_sorting.java

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

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();

        for (String s : strs) {
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }

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

49_solution3_frequency_serialization.java

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

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();

        for (String s : strs) {
            String key = serializeFrequency(s);
            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }

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

    private String serializeFrequency(String s) {
        int[] alphabet = new int[26];
        for (char c : s.toCharArray())
            alphabet[c - 'a']++;

        StringBuilder key = new StringBuilder();
        for (int i = 0; i < 26; i++)
            key.append(alphabet[i]).append('#');
        return key.toString();
    }
}

49_solution1_pairwise_comparison.js

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
  const result = [];

  for (const s of strs) {
    let placed = false;
    for (const group of result) {
      if (isAnagram(s, group[0])) {
        group.push(s);
        placed = true;
        break;
      }
    }

    if (!placed) {
      result.push([s]);
    }
  }

  return result;
};

function isAnagram(s, t) {
  if (s.length !== t.length) return false;

  const freq = new Map();
  for (const c of s) freq.set(c, (freq.get(c) || 0) + 1);
  for (const c of t) {
    const count = (freq.get(c) || 0) - 1;
    if (count < 0) return false;
    freq.set(c, count);
  }
  return true;
}

49_solution2_sorting.js

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
  const groups = new Map();

  for (const s of strs) {
    const key = s.split("").sort().join("");
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(s);
  }

  return Array.from(groups.values());
};

49_solution3_frequency_serialization.js

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
  const groups = new Map();

  for (const s of strs) {
    const key = serializeFrequency(s);
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(s);
  }

  return Array.from(groups.values());
};

function serializeFrequency(s) {
  const alphabet = new Array(26).fill(0);
  for (const c of s) alphabet[c.charCodeAt(0) - "a".charCodeAt(0)]++;

  return alphabet.join("#");
}

49_solution1_pairwise_comparison.py

from collections import Counter


class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        result = []

        for s in strs:
            placed = False
            for group in result:
                if self.isAnagram(s, group[0]):
                    group.append(s)
                    placed = True
                    break

            if not placed:
                result.append([s])

        return result

    def isAnagram(self, s: str, t: str) -> bool:
        return Counter(s) == Counter(t)

49_solution2_sorting.py

from collections import defaultdict


class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        groups = defaultdict(list)

        for s in strs:
            key = "".join(sorted(s))
            groups[key].append(s)

        return list(groups.values())

49_solution3_frequency_serialization.py

from collections import defaultdict


class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        groups = defaultdict(list)

        for s in strs:
            key = self.serializeFrequency(s)
            groups[key].append(s)

        return list(groups.values())

    def serializeFrequency(self, s: str) -> str:
        alphabet = [0] * 26
        for c in s:
            alphabet[ord(c) - ord("a")] += 1

        return "#".join(map(str, alphabet))

49_solution1_pairwise_comparison.rs

use std::collections::HashMap;

impl Solution {
    pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
        let mut result: Vec<Vec<String>> = Vec::new();

        for s in strs {
            let mut placed = false;
            for group in result.iter_mut() {
                if Solution::is_anagram(&s, &group[0]) {
                    group.push(s.clone());
                    placed = true;
                    break;
                }
            }

            if !placed {
                result.push(vec![s]);
            }
        }

        result
    }

    fn is_anagram(s: &str, t: &str) -> bool {
        if s.len() != t.len() {
            return false;
        }

        let mut freq: HashMap<char, i32> = HashMap::new();
        for c in s.chars() {
            *freq.entry(c).or_insert(0) += 1;
        }
        for c in t.chars() {
            let count = freq.entry(c).or_insert(0);
            *count -= 1;
            if *count < 0 {
                return false;
            }
        }
        true
    }
}

49_solution2_sorting.rs

use std::collections::HashMap;

impl Solution {
    pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
        let mut groups: HashMap<String, Vec<String>> = HashMap::new();

        for s in strs {
            let mut chars: Vec<char> = s.chars().collect();
            chars.sort_unstable();
            let key: String = chars.into_iter().collect();
            groups.entry(key).or_insert_with(Vec::new).push(s);
        }

        groups.into_values().collect()
    }
}

49_solution3_frequency_serialization.rs

use std::collections::HashMap;

impl Solution {
    pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
        let mut groups: HashMap<String, Vec<String>> = HashMap::new();

        for s in strs {
            let key = Solution::serialize_frequency(&s);
            groups.entry(key).or_insert_with(Vec::new).push(s);
        }

        groups.into_values().collect()
    }

    fn serialize_frequency(s: &str) -> String {
        let mut alphabet = [0; 26];
        for c in s.bytes() {
            alphabet[(c - b'a') as usize] += 1;
        }

        alphabet
            .iter()
            .map(|count| count.to_string())
            .collect::<Vec<String>>()
            .join("#")
    }
}