Given an array of strings, return all groups of strings that are anagrams. The groups must be created in order of their appearance in the original array. Look at the sample case for clarification.
Note: The final output will be in lexicographic order.
Example 1:
Input:
N = 5
words[] = {act,god,cat,dog,tac}
Output:
act cat tac 
god dog
Explanation:
There are 2 groups of
anagrams "god", "dog" make group 1.
"act", "cat", "tac" make group 2.
Example 2:
Input:
N = 3
words[] = {no,on,is}
Output: 
is
no on
Explanation:
There are 2 groups of
anagrams "is" makes group 1.
"no", "on" make group 2.
Your Task:
The task is to complete the function Anagrams() that takes a list of strings as input and returns a list of groups such that each group consists of all the strings that are anagrams.
Expected Time Complexity: O(N*|S|*log|S|), where |S| is the length of the strings.
Expected Auxiliary Space: O(N*|S|), where |S| is the length of the strings.
Constraints:
1<=N<=100
1<=|S|<=10

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def Anagrams(self, words, n):

        '''

        words: list of word

        n:      no of words

        return : list of group of anagram {list will be sorted in driver code (not word in grp)}

        '''

        

        #code here

Solutions:
class Solution:

	def Anagrams(self, words, n):
		d = dict()
		r = []
		for w in words:
			s = sorted(w)
			sw = ''.join(s)
			if sw in d:
				d[sw].append(w)
			else:
				d[sw] = [w]
		for i in d.values():
			r.append(i)
		return r


class Node:

	def __init__(self):
		self.childrens = [None] * 26
		self.words = []
		self.is_end_of_word = False

class Trie:

	def __init__(self):
		self.root = Node()

	def insert(self, root, word, i):
		chars = sorted(word)
		for ch in chars:
			idx = ord(ch) - ord('a')
			if root.childrens[idx] is None:
				root.childrens[idx] = Node()
			root = root.childrens[idx]
		root.is_end_of_word = True
		root.words.append(i)

	def get_anagrams(self, root, word):
		chars = sorted(word)
		for ch in chars:
			idx = ord(ch) - ord('a')
			root = root.childrens[idx]
		return root.words

class Solution:

	def Anagrams(self, words, n):
		try:
			t = Trie()
			for i in range(n):
				t.insert(t.root, words[i], i)
			ans = []
			for word in words:
				if word != '':
					anagrams = t.get_anagrams(t.root, word)
					temp = []
					for i in anagrams:
						temp.append(words[i])
						words[i] = ''
					ans.append(temp)
			return ans
		except Exception as e:
			print(e)
			return []


class Solution:

	def Anagrams(self, words, n):
		l = []
		x = set([''.join(sorted(i)) for i in words])
		for i in x:
			t = []
			for j in words:
				if sorted(i) == sorted(j):
					t.append(j)
			if t != [] and t not in l:
				l.append(t)
		return l


class Solution:

	def Anagrams(self, words, n):
		anagrams = {}
		for word in words:
			sorted_word = ''.join(sorted(word))
			if sorted_word in anagrams:
				anagrams[sorted_word].append(word)
			else:
				anagrams[sorted_word] = [word]
		return list(anagrams.values())


import collections

class Solution:

	def Anagrams(self, words, n):
		dic = collections.defaultdict(list)
		for word in words:
			sorted_word = ''.join(sorted(word))
			if sorted_word not in dic:
				dic[sorted_word].append(word)
			else:
				dic[sorted_word].append(word)
		return dic.values()


class Solution:

	def Anagrams(self, words, n):
		dic = {}
		lis = []
		for i in words:
			t = str(sorted(i))
			if t not in dic:
				dic[t] = [i]
				lis.append(t)
			else:
				dic[t].append(i)
		ans = []
		for i in lis:
			ans.append(dic[i])
		return ans


from collections import defaultdict

class Solution:

	def Anagrams(self, words, n):
		anagrams = defaultdict(list)
		for s in words:
			key = ''.join(sorted(s))
			anagrams[key].append(s)
		result = []
		for key in sorted(anagrams.keys()):
			result.append(anagrams[key])
		return result


from collections import defaultdict, Counter

class Solution:

	def Anagrams(self, words, n):
		m = defaultdict(list)
		for word in words:
			m[frozenset(dict(Counter(word)).items())].append(word)
		return [v for (k, v) in m.items()]


import collections

class Solution:

	def Anagrams(self, words, n):
		ans = collections.defaultdict(list)
		for s in words:
			count = [0] * 26
			for c in s:
				count[ord(c) - ord('a')] += 1
			ans[tuple(count)].append(s)
		return ans.values()


class Solution:

	def Anagrams(self, words, n):
		res = {}
		for word in words:
			ca = [c for c in word]
			ca.sort()
			s = ''.join(ca)
			if s not in res:
				res[s] = []
			res[s].append(word)
		return res.values()


class Solution:

	def Anagrams(self, words, n):
		g = {}
		ans = []
		for i in range(n):
			x = words[i]
			t = sorted(x)
			t = ''.join(t)
			if t not in g:
				g[t] = [x]
			else:
				g[t].append(x)
		for x in g:
			ans.append(g[x])
		return ans


class Solution:

	def Anagrams(self, words, n):
		d = dict()
		for i in words:
			val = ''.join(sorted(i))
			if val not in d:
				d[val] = [i]
			else:
				d[val].append(i)
		ans = []
		for v in d.values():
			ans.append(v)
		return ans


class Solution:

	def Anagrams(self, words, n):
		d = {}
		for i in words:
			chars = sorted(list(i))
			elem = ''.join(chars)
			if elem in d:
				d[elem].append(i)
			else:
				d[elem] = [i]
		return d.values()


class Solution:

	def Anagrams(self, words, n):
		mp = {}
		for idx in range(0, n):
			word = words[idx]
			key = ''.join(sorted(word))
			if key in mp:
				mp.get(key).append(word)
			else:
				mp[key] = [word]
		return mp.values()


class Solution:

	def Anagrams(self, words, n):
		st = ''.join(sorted(words[0]))
		di = {st: 0}
		li = [[words[0]]]
		j = 1
		for i in range(1, n):
			s = ''.join(sorted(words[i]))
			if s in di.keys():
				li[di[s]].append(words[i])
			else:
				di[s] = j
				j = j + 1
				li.append([words[i]])
		li.sort()
		return li


class Solution:

	def Anagrams(self, words, n):
		d = {}
		for i in range(n):
			word = ''.join(sorted(words[i]))
			d.setdefault(word, [])
			d[word].append(words[i])
		res = []
		for (k, v) in d.items():
			res.append(v)
		return res


class Solution:

	def Anagrams(self, strs, n):
		d = {}
		for i in range(len(strs)):
			c = [0] * 26
			for j in strs[i]:
				c[ord(j) - ord('a')] += 1
			if tuple(c) not in d:
				d[tuple(c)] = [strs[i]]
			else:
				d[tuple(c)].append(strs[i])
		return d.values()


class Node:

	def __init__(self):
		self.children = [None] * 26
		self.words = []
		self.is_end_of_word = False

class Trie:

	def __init__(self):
		self.root = Node()

	def insert(self, word, i):
		lst = list(word)
		lst.sort()
		root = self.root
		for ch in lst:
			idx = ord(ch) - ord('a')
			if root.children[idx] is None:
				root.children[idx] = Node()
			root = root.children[idx]
		root.is_end_of_word = True
		root.words.append(i)

	def search(self, word, i):
		lst = list(word)
		lst.sort()
		root = self.root
		for ch in lst:
			idx = ord(ch) - ord('a')
			if root.children[idx] is None:
				return []
			root = root.children[idx]
		if root.is_end_of_word and i in root.words:
			return root.words
		return []

class Solution:

	def Anagrams(self, words, n):
		t = Trie()
		for (idx, word) in enumerate(words):
			t.insert(word, idx)
		final_ans = []
		for i in range(len(words)):
			word = words[i]
			if word:
				ans = t.search(word, i)
				if ans:
					temp = []
					for idx in ans:
						temp.append(words[idx])
						words[idx] = ''
					final_ans.append(temp)
		final_ans.sort()
		return final_ans


class Solution:

	def Anagrams(self, words, n):
		d = dict()
		ans = []
		for i in range(n):
			temp = ''.join(sorted(words[i]))
			if temp not in d:
				d[temp] = [words[i]]
			else:
				d[temp].append(words[i])
		for k in d:
			ans.append(d[k])
		return ans


class Solution:

	def Anagrams(self, words, n):
		ans = {}
		for w in words:
			x = ''.join(sorted(w))
			if x not in ans:
				ans[x] = [w]
			else:
				ans[x].append(w)
		return ans.values()


class Solution:

	def Anagrams(self, strs, n):
		ans = {}
		for i in strs:
			word = ''.join(sorted(i))
			if word not in ans:
				ans[word] = [i]
			else:
				ans[word].append(i)
		return ans.values()


class Solution:

	def Anagrams(self, words, n):
		dict = {}
		list = []
		for i in words:
			t = str(sorted(i))
			if t not in dict:
				dict[t] = [i]
				list.append(t)
			else:
				dict[t].append(i)
		ans = []
		for i in list:
			ans.append(dict[i])
		return ans


class Solution:

	def Anagrams(self, words, n):
		if n == 0:
			return [['']]
		ans = {}
		for i in words:
			temp = ''.join(sorted(i))
			if temp in ans:
				ans[temp].append(i)
			else:
				ans[temp] = [i]
		return ans.values()


from collections import defaultdict

class Solution:

	def Anagrams(self, words, n):
		res = defaultdict(list)
		for s in words:
			order = [0] * 26
			for c in s:
				order[ord(c) - ord('a')] += 1
			res[tuple(order)].append(s)
		return res.values()


class Solution:

	def Anagrams(self, words, n):
		d = {}
		for ele in words:
			s_ele = ''.join(sorted(ele))
			if s_ele in d:
				d[s_ele] += [ele]
			else:
				d[s_ele] = [ele]
		return d.values()


class Solution:

	def Anagrams(self, words, n):
		arr = []
		for elm in words:
			temp = sorted(elm)
			temp = ''.join(temp)
			arr.append(temp)
		dic = {}
		for i in range(n):
			if arr[i] not in dic:
				dic[arr[i]] = words[i]
			else:
				dic[arr[i]] += ' ' + words[i]
		ans = []
		for elm in dic:
			temp = dic[elm].split()
			ans.append(temp)
		return ans


class Solution:

	def Anagrams(self, words, n):
		dict = {}
		for word in words:
			sortword = ''.join(sorted(word))
			if sortword not in dict:
				dict[sortword] = [word]
			else:
				dict[sortword] += [word]
		return [dict[i] for i in dict]


class Solution:

	def Anagrams(self, words, n):
		d = {}
		for i in words:
			if ''.join(sorted(i)) in d:
				d[''.join(sorted(i))].append(i)
			else:
				d[''.join(sorted(i))] = [i]
		res = d.values()
		return res


class Solution:

	def Anagrams(self, words, n):

		def convert(s):
			res = [0] * 26
			for char in s:
				res[ord(char) - ord('a')] += 1
			return tuple(res)
		rec = {}
		res = []
		for word in words:
			t = convert(word)
			if t in rec:
				res[rec[t]].append(word)
			else:
				res.append([word])
				rec[t] = len(res) - 1
		return res


class Solution:

	def Anagrams(self, words, n):

		def buildCountAndSay(string):
			occurences = {}
			for char in string:
				occurences[char] = occurences.get(char, 0) + 1
			countAndSay = ''
			for letter in range(97, 123):
				if occurences.get(chr(letter), 0) != 0:
					countAndSay = countAndSay + chr(letter) + str(occurences[chr(letter)])
			return countAndSay
		countAndSays = {}
		for word in words:
			countAndSay = buildCountAndSay(word)
			if countAndSay in countAndSays:
				countAndSays[countAndSay].append(word)
			else:
				countAndSays[countAndSay] = [word]
		return countAndSays.values()


class Solution:

	def Anagrams(self, words, n):
		hmap = {}
		for i in range(n):
			word = words[i]
			sorted_word = ''.join(sorted(word))
			if sorted_word in hmap:
				hmap[sorted_word].append(word)
			else:
				hmap[sorted_word] = [word]
		return list(hmap.values())


class Solution:

	def Anagrams(self, words, n):
		res = {}
		for i in words:
			s = str(sorted(i))
			if s in res:
				res[s].append(i)
			else:
				res[s] = [i]
		return list(res.values())


class Solution:

	def Anagrams(self, words, n):
		hashmap = {}
		for word in words:
			temp = [0] * 26
			for char in word:
				temp[ord(char) - ord('a')] += 1
			hashmap[tuple(temp)] = hashmap.get(tuple(temp), []) + [word]
		return hashmap.values()


class Solution:

	def Anagrams(self, strs, n):
		res = {}
		for word in strs:
			temp = ''.join(sorted(word))
			if temp in res:
				res[temp].append(word)
			else:
				res[temp] = [word]
		return sorted(res.values())


class Solution:

	def Anagrams(self, words, n):
		freq = {}
		for word in words:
			temp = ''.join(sorted(word))
			if temp in freq:
				freq[temp].append(word)
			else:
				freq[temp] = [word]
		res = []
		for val in freq.values():
			res.append(val)
		return res


class Solution:

	def Anagrams(self, words, n):
		dic = {}
		for i in words:
			s = ''.join(sorted(i))
			if s not in dic:
				dic[s] = []
			dic[s].append(i)
		groups = []
		for i in dic:
			groups.append(dic[i])
		groups.sort()
		return groups


import collections

class Solution:

	def Anagrams(self, words, n):
		d = collections.defaultdict(list)
		for i in range(len(words)):
			x = ''.join(sorted(words[i]))
			d[x].append(words[i])
		return d.values()


class Solution:

	def Anagrams(self, words, n):
		l = []
		for i in words:
			l += [''.join(sorted(i))]
		r = []
		k = 0
		d = {}
		for i in set(l):
			d[i] = [j for j in range(n) if l[j] == i]
		for i in d:
			r += [[words[j] for j in d[i]]]
		return r


class Solution:

	def Anagrams(self, words, n):
		dic = {}
		for word in words:
			sorted_word = ''.join(sorted(word))
			if sorted_word not in dic:
				dic[sorted_word] = [word]
			else:
				dic[sorted_word].append(word)
		return dic.values()


class Solution:

	def Anagrams(self, words, n):
		dict = {}
		for i in words:
			w = ''.join(sorted(i))
			if w in dict:
				dict[w].append(i)
			else:
				dict[w] = [i]
		return list(dict.values())


class Solution:

	def Anagrams(self, words, n):
		from collections import defaultdict
		m = []
		b = defaultdict(list)
		for i in words:
			b[''.join(sorted(i))].append(i)
		for i in b.values():
			m.append(i)
		return m


class Solution:

	def Anagrams(self, words, n):
		d = dict()
		for s in words:
			e = sorted(s)
			c = ''
			for i in e:
				c += str(i)
			if c not in d:
				d[c] = []
			d[c].append(s)
		v = []
		for (i, j) in d.items():
			v.append(j)
		return v


class Solution:

	def Anagrams(self, words, n):
		group = {}
		for word in words:
			key = str(sorted(word))
			if key in group:
				group[key].append(word)
			else:
				group[key] = [word]
		return list(group.values())


class Solution:

	def Anagrams(self, words, n):
		d = dict()
		a = []
		for ele in words:
			temp = tuple(sorted(ele))
			if temp in d.keys():
				d[temp].append(ele)
			else:
				d[temp] = [ele]
		for i in d:
			a.append(d[i])
		return a


class Solution:

	def Anagrams(self, words, n):
		maps = {}
		ans = []
		for i in words:
			j = sorted(i)
			o = ''.join(j)
			if o in maps.keys():
				maps[o] += ',' + i
			else:
				maps[o] = i
		for i in maps.values():
			ans.append(i.split(','))
		return ans


class Solution:

	def Anagrams(self, strs, n):
		l = {}
		for i in strs:
			j = list(i)
			j.sort()
			j = ''.join(j)
			l[j] = l.get(j, []) + [i]
		ans = []
		for i in l.values():
			ans.append(i)
		return ans


class Solution:

	def Anagrams(self, words, n):
		d = dict()
		for ele in words:
			a = tuple(sorted(ele))
			if a not in d:
				d[a] = [ele]
			else:
				d[a].append(ele)
		z = []
		for ele in d.keys():
			z.append(d[ele])
		z.sort()
		return z


import collections

class Solution:

	def Anagrams(self, words, n):
		anagramList = collections.defaultdict(list)
		for word in words:
			wordDict = [0] * 26
			for char in word:
				wordDict[ord(char) - ord('a')] += 1
			anagramList[' '.join((str(x) for x in wordDict))].append(word)
		result = []
		for (key, value) in anagramList.items():
			result.append(value)
		return result


class Solution:

	def Anagrams(self, words, n):
		hmap = {}
		for word in words:
			s = ''.join(sorted(word))
			if s in hmap:
				hmap[s].append(word)
			else:
				hmap[s] = [word]
		return list(hmap.values())


class Solution:

	def Anagrams(self, words, n):
		dic = {}
		for i in words:
			x = i
			x = ''.join(sorted(x))
			if x in dic.keys():
				dic[x].append(i)
			else:
				dic[x] = [i]
		ans = []
		for i in dic.keys():
			ans.append(dic[i])
		return ans


class Solution:

	def Anagrams(self, words, n):
		ans = []
		d = {}
		for i in words:
			tmp = tuple(sorted(i))
			if tmp in d:
				d[tmp].append(i)
			else:
				d[tmp] = [i]
		for i in d:
			ans.append(d[i])
		return ans


from collections import defaultdict
from collections import Counter

class Solution:

	def Anagrams(self, strs, n):
		c = defaultdict(list)
		for phrase in strs:
			sortedWord = ''.join(sorted(phrase))
			if sortedWord in c:
				c[sortedWord].append(phrase)
			else:
				c[sortedWord].append(phrase)
		return c.values()


from collections import defaultdict
from collections import Counter

class Solution:

	def Anagrams(self, words, n):
		res = []
		anagrams = []
		for i in range(n):
			c = Counter(words[i])
			c = {i: c[i] for i in c}
			anagrams.append(c)
		vis = set()
		for i in range(n):
			temp = []
			if i not in vis:
				vis.add(i)
				temp.append(words[i])
				for j in range(i + 1, n):
					if j not in vis and anagrams[i] == anagrams[j]:
						vis.add(j)
						temp.append(words[j])
			if temp:
				res.append(temp)
		return res


from collections import defaultdict

class Solution:

	def Anagrams(self, words, n):
		d = defaultdict(list)
		for i in words:
			s = ''.join((i for i in sorted(i)))
			d[s].append(i)
		temp = []
		for i in d:
			temp.append(d[i])
		return temp


class Solution:

	def Anagrams(self, words, n):
		dic = {}
		lis = []
		for i in words:
			j = list(i)
			j.sort()
			k = ''.join(j)
			if k not in dic:
				dic[k] = [i]
			else:
				dic[k].append(i)
		for i in dic:
			lis.append(dic[i])
		return lis


class Solution:

	def Anagrams(self, words, n):
		ans = []
		dict = {}
		for i in words:
			x = tuple(sorted(i))
			if x in dict:
				dict[x].append(i)
			else:
				dict[x] = [i]
		for i in dict:
			ans.append(dict[i])
		return ans


class Solution:

	def Anagrams(self, words, n):
		anagram_dict = {}
		sorted_words = []
		for word in words:
			word_lst = list(word)
			word_lst.sort()
			sorted_words.append(''.join(word_lst))
		for (i, word) in enumerate(words):
			if sorted_words[i] in anagram_dict:
				anagram_dict[sorted_words[i]].append(word)
			else:
				anagram_dict[sorted_words[i]] = [word]
		ans = []
		for (i, word) in enumerate(words):
			if sorted_words[i] in anagram_dict:
				ans.append(anagram_dict[sorted_words[i]])
				del anagram_dict[sorted_words[i]]
		return ans


from collections import defaultdict

class TrieNode:

	def __init__(self):
		self.children = {}
		self.isEndOfWord = False

def getNode():
	return TrieNode()

def chrToIndex(chr):
	return ord(chr) - ord('a')

class Trie:

	def __init__(self):
		self.root = getNode()

	def insert(self, key):
		pCrawl = self.root
		is_old_word = True
		for ch in key:
			if ch not in pCrawl.children:
				pCrawl.children[ch] = getNode()
				is_old_word = False
			pCrawl = pCrawl.children[ch]
		if not pCrawl.isEndOfWord:
			pCrawl.isEndOfWord = True
			is_old_word = False
		return is_old_word

class Solution:

	def Anagrams(self, words, n):
		anagram_dict = defaultdict(list)
		tr = Trie()
		for word in words:
			sorted_word = ''.join(sorted(word))
			is_visited = tr.insert(sorted_word)
			if is_visited:
				anagram_dict[sorted_word].append(word)
			else:
				anagram_dict[sorted_word] = [word]
		res = []
		for (key, values) in anagram_dict.items():
			res.append(values)
		return res


from collections import Counter, defaultdict

class Solution:

	def Anagrams(self, words, n):
		d = {}
		for i in words:
			k = ''.join(sorted(i))
			if k in d:
				d[k].append(i)
			else:
				d[k] = [i]
		return d.values()


class Node:

	def __init__(self):
		self.ix = []
		self.children = [None] * 26

class Solution:

	def Anagrams(self, words, n):
		trie = Node()
		ans = []

		def insert(j, word):
			root = trie
			for w in word:
				i = ord(w) - ord('a')
				if not root.children[i]:
					root.children[i] = Node()
				root = root.children[i]
			root.ix.append(j)

		def dfs(root):
			if len(root.ix) > 0:
				ans.append([words[i] for i in root.ix])
			for child in root.children:
				if child:
					dfs(child)
		for (j, w) in enumerate(words):
			insert(j, sorted(list(w)))
		dfs(trie)
		return ans


class Solution:

	def Anagrams(self, words, n):
		hash_map = {}
		for w in words:
			sorted_w = ''.join(sorted(w))
			if hash_map.get(sorted_w):
				hash_map[sorted_w].append(w)
			else:
				hash_map[sorted_w] = [w]
		ans = []
		for (k, v) in hash_map.items():
			ans.append(v)
		return ans


from collections import defaultdict

class Solution:

	def Anagrams(self, words, n):
		d = defaultdict(list)
		for word in words:
			sortw = ''.join(sorted(word))
			if sortw not in d:
				d[sortw] = [word]
			else:
				d[sortw].append(word)
		return d.values()


import collections

class Solution:

	def Anagrams(self, words, n):
		result = collections.defaultdict(list)
		for string in words:
			hashmap = [0] * 26
			for c in string:
				hashmap[ord(c) - ord('a')] += 1
			result[tuple(hashmap)].append(string)
		return result.values()


class Solution:

	def Anagrams(self, words, n):
		ans = []
		d = dict()
		for i in range(len(words)):
			temp = tuple(sorted(words[i]))
			if temp in d:
				d[temp].append(words[i])
			else:
				d[temp] = [words[i]]
		for i in d:
			ans.append(d[i])
		return ans


class Solution:

	def Anagrams(self, words, n):
		ans = []
		d = {}
		for i in words:
			temp = tuple(sorted(i))
			if temp not in d:
				d[temp] = [i]
			else:
				d[temp].append(i)
		for j in d:
			ans.append(d[j])
		return ans


class Solution:

	def Anagrams(self, words, n):
		anagrams_dict = {}
		for word in words:
			sorted_word = ''.join(sorted(word))
			if sorted_word not in anagrams_dict:
				anagrams_dict[sorted_word] = [word]
			else:
				anagrams_dict[sorted_word].append(word)
		result = []
		for key in anagrams_dict:
			result.append(anagrams_dict[key])
		return result


class Solution:

	def Anagrams(self, words, n):
		a = []
		d = {}
		for i in words:
			t = tuple(sorted(i))
			if t in d:
				d[t].append(i)
			else:
				d[t] = [i]
		for i in d:
			a.append(d[i])
		return a


class Solution:

	def Anagrams(self, words, n):
		from collections import defaultdict
		mp = defaultdict(list)
		for w in words:
			sig = ''.join(sorted(w))
			mp[sig].append(w)
		ans = []
		for sig in sorted(mp.keys()):
			ans.append(mp[sig])
		return ans


class Solution:

	def Anagrams(self, words, n):
		d = {}
		for i in words:
			sortword = ''.join(sorted(i))
			if sortword in d:
				d[sortword].append(i)
			else:
				d[sortword] = [i]
		ans = []
		for item in d.values():
			ans.append(item)
		return ans