Algorithm
Problem Name: 49. Group Anagrams
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
Input: strs = ["eat","tea","tan","ate","nat","bat"] Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Example 2:
Input: strs = [""] Output: [[""]]
Example 3:
Input: strs = ["a"] Output: [["a"]]
Constraints:
1 <= strs.length <= 1040 <= strs[i].length <= 100strs[i]consists of lowercase English letters.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
typedef struct res_s {
char ***p;
int *csz;
int *cl;
int sz;
int n;
} res_t;
typedef struct e_s {
char *key;
int k;
struct e_s *shadow;
} e_t;
#define HSZ 1021
int new_buff(res_t *res) {
int k, buffsz = 10;
char **buff = malloc(buffsz * sizeof(char *));
//assert(buff);
if (res->sz == 0) {
res->sz = 100;
res->p = malloc(res->sz * sizeof(char **));
res->csz = malloc(res->sz * sizeof(int));
res->cl = malloc(res->sz * sizeof(int));
//assert(res->p && res->csz && res->cl);
} else if (res->sz == res->n) {
res->sz *= 2;
res->p = realloc(res->p, res->sz * sizeof(char **));
res->csz = realloc(res->csz, res->sz * sizeof(int));
res->cl = realloc(res->cl, res->sz * sizeof(int));
//assert(res->p && res->csz && res->cl);
}
k = res->n ++;
res->p[k] = buff;
res->csz[k] = buffsz;
res->cl[k] = 0;
return k;
}
void add2res(res_t *res, int k, char *str) {
if (res->csz[k] == res->cl[k]) {
res->csz[k] *= 2;
res->p[k] = realloc(res->p[k], res->csz[k] * sizeof(char **));
//assert(res->p[k]);
}
res->p[k][res->cl[k] ++] = str;
}
int cmp(const void *a, const void *b) {
return *(char *)a - *(char *)b;
}
int hash_code(char *key) {
int h = 5381;
while (*key) {
h = h * 33 + *key;
key ++;
}
return h;
}
int lookup(e_t **ht, int code, char *key) {
e_t *e = ht[code % HSZ];
while (e && strcmp(e->key, key)) {
e = e->shadow;
}
if (e) return e->k;
return -1;
}
void insert(e_t **ht, int code, char *key, int k) {
e_t *e = malloc(sizeof(e_t));
//assert(e);
e->key = key;
e->k = k;
e->shadow = ht[code % HSZ];
ht[code % HSZ] = e;
}
char*** groupAnagrams(char** strs, int strsSize, int** columnSizes, int* returnSize) {
res_t res = { 0 };
e_t *ebuff[HSZ * 2] = { 0 };
e_t **ht = &ebuff[HSZ];
int i, k, code;
char *str, *key;
for (i = 0; i < strsSize; i ++) {
str = strs[i];
key = strdup(str);
qsort(key, strlen(key), sizeof(char), cmp);
code = hash_code(key);
k = lookup(ht, code, key);
if (k == -1) {
k = new_buff(&res);
insert(ht, code, key, k);
} else {
free(key);
}
add2res(&res, k, str);
}
// TODO: clean hash table
free(res.csz);
*columnSizes = res.cl;
*returnSize = res.n;
return res.p;
}
Input
strs = ["eat","tea","tan","ate","nat","bat"]
Output
[["bat"],["nat","tan"],["ate","eat","tea"]]
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<vector<string>> groupAnagrams(vector < string>& strs) {
vector<vector<string>>res;
unordered_map < string, vector<string>>m;
for(auto s: strs){
string tmp = s;
sortStr(tmp);
m[tmp].push_back(s);
}
for(auto x: m) res.push_back(x.second);
return res;
}
void sortStr(string& s){
unordered_map < char, int>m;
for(auto c: s) m[c]++;
string res = "";
for(int i = 0; i < 26; i++){
while(m['a' + i]-- > 0) res.push_back('a' + i);
}
s = res;
}
};
Input
strs = [""]
Output
[""]]
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public List(
Arrays.stream(strs).collect(Collectors.groupingBy(Solution::getCodedString)).values());
}
public static String getCodedString(String s) {
return s.chars()
.mapToObj(c -> (char) c)
.sorted()
.map(Object::toString)
.collect(Collectors.joining());
}
}
Input
strs = ["a"]
Output
[["a"]]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const groupAnagrams = (strs) => {
const resp = new Array(),
termsGrouped = new Map()
strs.forEach((term) => {
const hashed = hash(term)
if (!termsGrouped.has(hashed)) termsGrouped.set(hashed, new Array())
termsGrouped.get(hashed).push(term)
})
termsGrouped.forEach((terms) => {
resp.push(terms)
})
return resp
}
const hash = (term) => {
const arr = Array(26).fill(0)
const a = 'a'.charCodeAt(0)
for(let i = 0, len = term.length; i < len; i++) {
arr[term[i].charCodeAt(0) - a]++
}
return arr.join('-')
}
Input
strs = ["eat","tea","tan","ate","nat","bat"]
Output
[["bat"],["nat","tan"],["ate","eat","tea"]]
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def groupAnagrams(self, strs):
dic = collections.defaultdict(list)
for s in strs:
dic["".join(sorted(s))].append(s)
return list(dic.values())
Input
strs = [""]
Output
[[""]]
#6 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Collections.Generic;
using System.Linq;
namespace LeetCode
{
public class _049_GroupAnagrams
{
public IList < IList());
}
mapping[key].Add(str);
}
var result = new List < IList s).ToList());
}
return result;
}
}
}
Input
strs = ["a"]
Output
[["a"]]