[LeetCode] #49: Group Anagrams

Kyu Hwan Choi·2022년 4월 28일
0

LeetCode

목록 보기
2/11
post-thumbnail

Problem:

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.


Process:

Objective: Returning array of string arrays where each string arrays are group of anagrams.

Constraints:
1. 1 <= strs.length <= 10^4
2. 0 <= strs[i].length <= 100
3. strs[i] consists of lowercase English letters.

Additional Details:
1. When the input string list is empty, return empty string list.

  1. The groups can be in any order.

Breakdown:

Grouping Anagrams

An anagram is a word or phrase formed by rearranging the letters of a word, using all the original letters exactly once.

We have to see if a word has the same combination of letter(same # of each letters) compared to other words.

Simplify!

If we were to find the anagrams of a particular word from the word list...
1. We count the number of each letter present in the word
2. We traverse through the word list while comparing the letter combination of each word to the target word.
*We can use hash map to keep track of the combination of letters.

What I could possibly do...
Let's say we keep the letter combination of each word in a hash map. This would take O(n) where n is the total number of letters in all the words combined.

then, we could use that particular hash map as a key and keep the word list as value. However, dictionary is not hashable.

Would there be a better way to store the combination as a data type other than hash map? What if I kept two seperate list of words and the letter combination of each word? We need to use hash map for quick search.


Solution:

Approach #1: Use hash map to keep track of letter combinations and loop through the list of words to group anagrams.

  • Time Complexity: O(n^2) where n is the length of strs list
  • Space Complexity: O(2n)

How it works:
1. Create a seperate list of letter combination
2. Loop through the letter combination list to see if there are identical ones. We will append the letters with same combinations together. (We will count if we came across each indicies)

def findLetterComb(self, word:str):
        letter_comb = {}
        for letter in word:
            if letter in letter_comb:
                letter_comb[letter] += 1
            else:
                letter_comb[letter] = 1
        
        return letter_comb
            
    
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        letter_comb_lst = []
        
        # Finding letter combination of each words in strs
        for word in strs:
            letter_comb = self.findLetterComb(word)
            letter_comb_lst.append(letter_comb)
            
        # Grouping anagrams according to the letter combination of each words
        index_count = set()
        anagram_group_lst = []
        for i in range(len(letter_comb_lst)):
            
            if i in index_count:
                continue
                
            group = [strs[i]]
            comb = letter_comb_lst[i]
            
            for j in range(i+1,len(letter_comb_lst)):
                
                # If letter combination is identical, group them.
                if letter_comb_lst[i] == letter_comb_lst[j]:
                    group.append(strs[j])
                    index_count.add(j)
            
            index_count.add(i)
            anagram_group_lst.append(group)
                       
        return anagram_group_lst

Limitations:
1. This code is too slow. There must be a way that I could make this more efficient.


Approach #2: Inputting to hash map with sorted str keys

  • Time Complexity: O(n^2logn)
  • Space Complexity: O(n)

How it works:
1. Iterate through each word in strs
2. Use the tuple(sorted(word)) as the key of dictionary to input word into dictionary
3. Return dictionary values.

    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        group_dict = {}
        for word in strs:
            sorted_word = tuple(sorted(word))
            group_dict[sorted_word] = group_dict.get(sorted_word, []) + [word]
        return group_dict.values()

Something that I have learned:

  • dict.get(key, value):
    • key: key searched on the dictionary
    • value: value to be returned if the key is not found in the dictionary

LeetCode Question #49

0개의 댓글