[Algorithm] LeetCode - 49. Group Anagrams (Hash Table, Sorting, String)

 

LeetCode 문제입니다.

[문제설명]

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.

 

번역)

문자열 배열이 주어지면 "Anagram은"을 함께 그룹화하십시오.
어떤 순서로든 답변을 반환할 수 있습니다.

"Anagram"은 일반적으로 모든 원래 문자를 정확히 한 번 사용하여 다른 단어 또는 구의 문자를 재배열하여 형성된 단어 또는 구입니다.

 

Topic: Hash Table, Sorting, String

Level: Medium

Accepted 1,308,247 / Submissions 2,044,695

---

[제한사항]

 

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

 

---

[입출력]

예시 1

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

 

예시 2

Input: strs = [""]
Output: [[""]]

 

예시 3

Input: strs = ["a"]
Output: [["a"]]

---

[문제풀이]

1. 실패한 코드 (Time Limit Exceeded)

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
const groupAnagrams = (strs) => {
    const checkAnagram = (word, comparingWord) => {
        const arrangedWord = word.split("").sort().join("")
        const arrangedComparingWord = comparingWord.split("").sort().join("")
        return arrangedWord === arrangedComparingWord
    }
    
    return strs.reduce((acc,  cur) => {
        let tmp = acc
        if (acc.length === 0) {
            tmp.push([cur])
        } else {
            
            Loop1: for (let i = 0; i < tmp.length; i++) {
                const isAnagram = checkAnagram(tmp[i][0], cur)
                if (isAnagram) {
                    tmp[i].push(cur)
                    break Loop1
                } else if (i === tmp.length -1) {
                    tmp.push([cur])
                    break Loop1
                }
            }
        }
        return tmp
    }, [])    
};

Failure: 

첫번째 코드에서 보기 좋게 time limit이 걸렸다.

topic이 hash인것도 모르고 무식하게 array에서 linear search를 했기 때문!

time limit이 난 input을 보니 strs 배열의 item들이 대부분 문자열 크기가 다르고 grouping되는 아나그램이 거의 없었다.

따라서 linear search만 하다가 time complexity에서 꽝이 난것.

 

2. 성공한 코드

 

const groupAnagrams = (strs) => {
    // (1) make a map for storing key, value
    let map = new Map();
    
    // (2) strs 배열의 item(s)마다 문자열을 분리하고, sort하여 다시 join한다.
    // 이 과정의 목적은 anagram이라면 모두 같은 리턴 값을 갖기 때문
    // 이 return 값의 Key가 있다면, value (array type)에 Push, 없다면 key와 함께 [s]를 세팅한다.
    for (let s of strs) {
        let tmp = s.split('').sort().join('')
        if (map.has(tmp)) map.get(tmp).push(s)
        else map.set(tmp, [s])
    }

    // (3) map의 value들을 return
    return [...map.values()]

};

 

Idea: 

1. key, value를 저장할 Map 생성

2. strs의 배열은 Items(s)마다 문자열을 분리하고, ...

3. map의 value들을 return

 

어쩌다보니 영어 주석을 까먹은...

---

 

[Performance]