Hyuntae H

Hyuntae H

배워가는 학생
21.03.29~22.09.28 군대

Python Algorithm Q5

Q5 groups-anagrams

Q

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.

Sample Input

Input: strs = [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”] Output: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]

Input: strs = [””] Output: [[””]]

Input: strs = [“a”] Output: [[“a”]]

Constraints

  • 1 <= strs.length <= 104
  • 0 <= strs[i].length <= 100
  • strs[i] consists of lowercase English letters.

1. My Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        dic={}
        for words in strs:
            dic[''.join(sorted(words))]=[]

        for words in strs:
            dic[''.join(sorted(words))].append(words)
        return (list(dic.values()))

#for testing
a = Solution()
s = ["eat","tea","tan","ate","nat","bat"]
print(a.groupAnagrams(s))

The most efficient way to solve anagram problem is to sorting. By sorting words, you can get unified result.
Build the dictionary, whose keys are sorted words and value is empty list. Then iterate the dic again for appending the values(words) type of dic.values() is literally dic_values, so change it to list.

2. Given Solution

1
2
3
4
5
6
7
8

def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams = collections.defaultdict(list) '''collections.defaultdict is similiar to python dict,
        but it tolerates the error when approaching to the key that doesn't exist '''

        for words in strs:
            anagrams[''.join(sorted(words))].append(words)
        return list(dic.values())

Almost similiar to my answer. Just one thing different from mine is is that given answer used the dictionary from the collections library. You can test by using “anagrams={}” instead of “anagrams = collections.defaultdict(list)”. Using the first one, KeyError occurs. Conciously using the dict from collections rather than original.

Overall Review

Easy one, but it’s little bit complicated because of lack of proficiency in handling python dictionary. My own soltuion code is more than necessary compared to the given one. One more loop is needlessly writtened because I’d never noticed that defining dic(without collections library) caused the KeyError. I must take more time to be proficient in handling dictionary.

참고