medium
submitted(failed due to exceed runtime):
class Solution(object):
def isAnagram(self, s, t):
if len(s) != len(t):
return False
letter = {}
letter2 = {}
for i in s:
if i not in letter:
letter[i] = 1
else:
letter[i] += 1
for i in t:
if i not in letter2:
letter2[i] = 1
else:
letter2[i] += 1
if letter != letter2:
return False
else:
return True
def groupAnagrams(self, strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
output = []
searched = []
for i in strs:
i_index = strs.index(i)
temp_strs = strs[i_index+1:]
if i in searched:
continue
tempList = []
tempList.append(i)
for j in temp_strs:
if self.isAnagram(i, j) == True:
tempList.append(j)
if j not in searched:
searched.append(j)
print(tempList)
output.append(tempList)
return output
accepted answer:
class Solution(object):
def groupAnagrams(self, strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
res = defaultdict(list)
for s in strs:
count = [0] * 26
for c in s:
count[ord(c) - ord("a")] += 1
res[tuple(count)].append(s)
return res.values()
Explaination: This basically means that the program is counting the letter count of the a word, and turn it into a key to the dictionary. Then it will use this key compare it against the key generated based on the next word. the keys match, the program put tha word in list, and it output it in the end. The dictionary will look like:
[key]:[list of words with same key]
...
This has a run time of O(number of string * number of chatacter)
count[ord(c) - ord("a")] += 1
This line takes the ascii number of the current chatacter, and minus it with the ascii number of "a", which is the equivelent of getting the index number of this chatacter in relation to the alphabet.