[string] group anagrams

✅ Problem

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

 

✅ Approach & Solution

방식1)

• 주어진 문자열 하나씩 비교한다.
  • 이중 for문 형태
  • 이미 그룹에 포함된 문자열은 이후 비교할 때 제외한다.

• 두 문자열이 애너그램인지 어떻게 확인할까?
  • 문자열의 길이가 다른 경우 애너그램이 아니다.
  • 문자열의 길이가 같은 경우
    • 철자가 동일한지 확인한다.
      • 방안1) 알파벳 등장 횟수 비교 : Map 사용
      • 방안2) 문자열 사전식 정렬 후 두 문자열이 동일한지 확인

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

        int[] check = new int[strs.length]; // 이미 그룹에 포함되었는지 확인용 배열 : 1=true, 0=false

        for (int i = 0; i < strs.length; i++) {
            if (check[i] == 0) { // 그룹에 포함되지 않았을 때
                String value = strs[i];
                
                List<String> group = new ArrayList<>();
                group.add(value);

                for (int j = i + 1; j < strs.length; j++) {
                    if (check[j] == 0) { // 그룹에 포함되지 않았을 때
                        String target = strs[j];
                        if (isAnagram(value, target)) {
                            group.add(target);
                            check[j] = 1;
                        }
                    }
                }

                result.add(group);
                check[i] = 1;
            }
        }
        
        return result;
    }

    public boolean isAnagram(String a, String b) {
        boolean result = true;

        if (a.length() != b.length()) {
            result = false;
        } else {
            // a의 알파벳 등장 횟수 저장
            // b의 알파벳에 대해 a의 등장 횟수에서 차감
            Map<Character, Integer> spellingMap = new HashMap<>();

            for (int i = 0; i < a.length(); i++) {
                int cnt = spellingMap.getOrDefault(a.charAt(i), 0);
                spellingMap.put(a.charAt(i), cnt + 1);
            }

            for (int j = 0; j < b.length(); j++) {
                int cnt = spellingMap.getOrDefault(b.charAt(j), 0);
                if (cnt - 1 < 0) {
                    result = false;
                    break;
                } else {
                    spellingMap.put(b.charAt(j), cnt - 1);
                }
            }

        }

        return result;
    }

}

 

방식2)

• 문자열 사전식 정렬 후 그룹에 추가

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 문자열 사전식 정렬 -> 동일한 문자열 일 때 그룹에 추가
        
        Map<String, List<String>> groupMap = new HashMap<>();

        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);

            String key = String.valueOf(chars); // 사전식 정렬된 배열을 문자열로 변환
            if (!groupMap.containsKey(key)) {
                groupMap.put(key, new ArrayList<>());
            }
            groupMap.get(key).add(str);
        }

        return new ArrayList<>(groupMap.values());
    }
}