In the Leetcode Group Anagrams problem solution 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 <= 104
- 0 <= strs[i].length <= 100
- strs[i] consists of lowercase English letters.
Solution in C Programming
#define HASHSZ 200
typedef struct node node;
struct node {
int cnt[26];
int idx;
node *next;
};
/* accumulate each count for hash function */
int hashFunc(int *cnt)
{
int val = 0;
for(int i = 0; i < 26; i++) {
val += cnt[i];
}
return (val % HASHSZ);
}
node ** initTable(void)
{
node **table = (node **) malloc(sizeof(node *) * HASHSZ);
memset(table, 0, sizeof(node *) * HASHSZ);
return table;
}
int findTable(node **table, int val, int *cnt)
{
node *head = table[val];
while(head) {
if(0 == memcmp(head->cnt, cnt, sizeof(int) * 26)) {
return head->idx;
}
head = head->next;
}
return -1;
}
void insertTable(node **head, int *cnt, int index)
{
node *new = (node *) malloc(sizeof(node));
memcpy(new->cnt, cnt, sizeof(int) * 26);
new->idx = index;
new->next = *head;
*head = new;
}
char *** groupAnagrams(char ** strs, int strsSize, int* returnSize, int** returnColumnSizes){
//iterate n strings
//increase letter count
//use the value to be hash, insert or get index
int i, j, idx, col, sz, val;
int cnt[26];
*returnSize = 0;
*returnColumnSizes = (int *) malloc(sizeof(int) * strsSize);
memset(*returnColumnSizes, 0, sizeof(int) * strsSize);
char ***returnBuf = (char ***) malloc(sizeof(char **) * strsSize);
for(i = 0; i < strsSize; i++) {
//dynamic alloc
returnBuf[i] = (char **)malloc(sizeof(char *));
}
node **tbl = initTable();
for(i = 0; i < strsSize; i++) {
memset(cnt, 0, sizeof(int) * 26);
sz = strlen(strs[i]);
for(j = 0; j < sz; j++) {
cnt[strs[i][j] - 'a']++;
}
val = hashFunc(cnt);
idx = findTable(tbl, val, cnt);
if(idx == -1) {
//get new index
idx = *returnSize;
insertTable(&tbl[val], cnt, idx);
(*returnSize)++;
}
char *str = malloc(sizeof(char) * (sz + 1));
strcpy(str, strs[i]);
col = (*returnColumnSizes)[idx];
(*returnColumnSizes)[idx]++;
returnBuf[idx] = realloc(returnBuf[idx], sizeof(char *) * (*returnColumnSizes)[idx]);
returnBuf[idx][col] = str;
}
for(i = (*returnSize); i < strsSize; i++) {
free(returnBuf[i]);
}
returnBuf = realloc(returnBuf, sizeof(char **) * (*returnSize));
*returnColumnSizes = realloc(*returnColumnSizes, sizeof(int) * (*returnSize));
return returnBuf;
}Solution in C++ Programming
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> strMap;
for (int i = 0; i < strs.size(); i++) {
string strCode = generateStrCode(strs[i]);
strMap[strCode].push_back(strs[i]);
}
vector<vector<string>> result;
for (auto i = strMap.begin(); i != strMap.end(); i++) {
result.push_back(i->second);
}
return result;
}
string generateStrCode(string s) {
vector<int> container(26, 0);
for (int i = 0; i < s.size(); i++) {
container[s[i] - 'a']++;
}
string code = "";
for (int i = 0; i < container.size(); i++) {
if (container[i] > 0) {
char c = 'a' + i;
code += to_string(container[i]) + c;
}
}
return code;
}
};Solution in Java Programming
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
if(strs == null || strs.length == 0) return new ArrayList<>();
Map<String,List<String>> result = new HashMap<>();
for(String ana : strs){
char[] chars = ana.toCharArray();
Arrays.sort(chars);
String key = String.valueOf(chars);
if(!result.containsKey(key)) result.put(key,new ArrayList<>());
result.get(key).add(ana);
}
return new ArrayList<>(result.values());
}
}Solution in Python Programming
class Solution:
def groupAnagrams(self, strs):
ans = defaultdict(list)
for string in strs:
cnt = [0] * 26 #a-z
for char in string:
cnt[ord(char) - ord("a")] +=1
ans[tuple(cnt)].append(string)
return ans.values()Solution in C# Programming
public class Solution {
public IList<IList<string>> GroupAnagrams(string[] strs)
{
List<IList<string>> resultList = new List<IList<string>>();
Dictionary<string, List<string>> dict = new Dictionary<string, List<string>>();
foreach (string s in strs)
{
char[] arr = s.ToCharArray();
Array.Sort(arr);
string key = String.Join("", arr);
if (!dict.ContainsKey(key))
{
dict.Add(key, new List<string>());
}
dict[key].Add(s);
}
foreach (var key in dict)
{
resultList.Add(key.Value);
}
return resultList;
}
}Also read,