리트코드 데일리과제(3/26) - 916. Word Subsets

leetcode.com/problems/word-subsets/

Word Subsets - LeetCode

1. 유형

구현

 

2. 풀이

접근법 1) 해쉬맵

 

B의 각 요소별 최대값을 해쉬맵으로 구현한다.

 

즉, B [e, oo] 라고 치면

 

<e, 1> <o, 2> 라고 저장하는 방법이다.

 

그리고 마지막에 A도 같은 방식으로 딕셔너리를 만들어주고, 딕셔너리B하고 비교하여

 

A딕셔너리가 B의 딕셔너리보다 더 크면 포함관계다.

 

예를들어 A의 facebook이 있다면, <f, 1> <a, 1> <c. 1> <e, 1> <b, 1> <o,2> <k, 1>

이 완성된다. 이 각 요소들이 <e 1> <o, 2> 보다 크거나 같으면 된다.

 

접근법 2) 배열

 

배열 접근법도 위의 방식과 동일하다, 하지만 딕셔너리를 해쉬맵이 아니라

 

배열로 만들면 된다.

 

facebook으로 예를들면

 

arr[f-'a']++ 이런 식으로 구하면됨.

 

3. 코드

class Solution {
    public List<String> wordSubsets(String[] A, String[] B) {
        HashMap<Character, Integer> mapB = new HashMap<>();
        HashMap<Character, Integer> mapA = new HashMap<>();
        List<String> ans = new ArrayList<>();
        //딕셔너리 만들기
        for(String s : B){
            HashMap<Character, Integer> temp = new HashMap<>();
            for(int i=0; i<s.length(); i++){
                int n = temp.getOrDefault(s.charAt(i), 0);
                temp.put(s.charAt(i), n+1);
            }
            Set<Character> keys = temp.keySet();
            for(Character key : keys){
                int global = mapB.getOrDefault(key, 0);
                int local = temp.get(key);
                if(local > global){
                    mapB.put(key, local);
                }
            }
        }
        for(String s : A){
            HashMap<Character, Integer> temp = new HashMap<>();
            for(int i=0; i<s.length(); i++){
                int n = temp.getOrDefault(s.charAt(i), 0);
                temp.put(s.charAt(i), n+1);
            }
            Set<Character> keys = mapB.keySet();
            boolean flag = true;
            for(Character key: keys){
                int b = mapB.get(key);
                int a = temp.getOrDefault(key, 0);
                if(b > a){
                    flag = false;
                    break;
                }
            }
            if(flag){
                ans.add(s);
            }
        }        
        return ans;
    }
}

모범답안

class Solution {
    public List<String> wordSubsets(String[] A, String[] B) {
        int[] bmax = count("");
        for (String b: B) {
            int[] bCount = count(b);
            for (int i = 0; i < 26; ++i)
                bmax[i] = Math.max(bmax[i], bCount[i]);
        }

        List<String> ans = new ArrayList();
        search: for (String a: A) {
            int[] aCount = count(a);
            for (int i = 0; i < 26; ++i)
                if (aCount[i] < bmax[i])
                    continue search;
            ans.add(a);
        }

        return ans;
    }

    public int[] count(String S) {
        int[] ans = new int[26];
        for (char c: S.toCharArray())
            ans[c - 'a']++;
        return ans;
    }
}