[LeetCode] Group Anagrams

https://leetcode.com/problems/group-anagrams/

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.
 
Example 1:
Input: strs = ["eat","tea","tan","ate","nat","bat"] Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Example 2:
Input: strs = [""] Output: [[""]]
Example 3:
Input: strs = ["a"] Output: [["a"]]
 
Constraints:
1 <= strs.length <= 1040 <= strs[i].length <= 100strs[i] consists of lowercase English letters.

 

쉽지 않은 문제였습니다. 처음 글자를 비교하는 메서드에서 List를 사용하는 바람에 시간 초과가 되었네요. 이 후 charArray로 타입을 바꾸면서 문제는 해결되었습니다만 아직까지 속도가 많이 느린 로직입니다. 개선을 해야겠네요.

 

쉽게 주어지는 strs를 순회하면서 anagram인지 체크하고, anagram으로 선정 된 문자는 완료(DONE)라는 문자열을 주어 다시 비교하지 않게 하였습니다.

 

anagram인지 체크는 배열로 변환 후 정렬을 사용했습니다. 실제로 acc와 ac는 같은 문자가 아니기 때문에 size가 다른 경우에도 anagram이 아니도록 하였습니다.

 

아래는 코드입니다.

 

import java.util.*;

class Solution {
    private final static String DONE = "DONE";

    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> answers = new ArrayList<>();

        for (int i = 0; i < strs.length; i++) {
            if (strs[i].equals(DONE)) {
                continue;
            }

            List<String> answer = new ArrayList<>();
            answer.add(strs[i]);

            for (int j = i; j < strs.length ; j++) {

                if (i == j || strs[j].equals(DONE)) {
                    continue;
                }

                if (isSame(strs[i], strs[j])) {
                    answer.add(strs[j]);
                    strs[j] = DONE;
                }
            }

            answers.add(answer);
        }

        return answers;
    }

   private boolean isSame(String origin, String target) {
        if (origin.length() != target.length()) {
            return false;
        }

        char[] baseValue = origin.toCharArray();
        Arrays.sort(baseValue);

        char[] compareToValue = target.toCharArray();
        Arrays.sort(compareToValue);

        for (int i = 0; i < baseValue.length; i++) {
            if (baseValue[i] != compareToValue[i]) {
                return false;
            }
        }
        return true;
    }
}

 

 

이 후 소스 코드 수정을 하였습니다. hashMap을 사용하였습니다. map의 키로는 정렬이 된 원소가 들어가고, 밸류에는 List<String> 타입으로 같은 그룹의 문자열을 계속해서 add 하였습니다. 속도가 더 줄긴 했네요. 아래는 소스코드 입니다.

 

import java.util.*;

public class GroupAnagrams {
    private HashMap<String, List<String>> hashMap = new HashMap<>();

    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> answers = new ArrayList<>();

        for (String str : strs) {
            sorting(str);
        }

        for (Map.Entry<String, List<String>> entry : hashMap.entrySet()) {
            answers.add(entry.getValue());
        }

        return answers;
    }

    private void sorting(String target) {
        char[] compareToValue = target.toCharArray();
        Arrays.sort(compareToValue);
        String sortedTarget = new String(compareToValue);

        if (hashMap.containsKey(sortedTarget)) {
            List<String> strings = hashMap.get(sortedTarget);
            strings.add(target);
            return;
        }

        hashMap.put(sortedTarget, new ArrayList<>(List.of(target)));
    }
}