Leetcode 1002. Find Common Characters

Given a string array words, return an array of all characters that show up in all strings within the words (including duplicates). You may return the answer in any order.

문자열 배열을 주어졌을 때, 모든 문자열에 공통으로 들어있는 문자들을 구하시오. 리턴 값의 순서는 상관없음.

Example 1:

Input: words = ["bella","label","roller"]

Output: ["e","l","l"]

 

Example 2:

Input: words = ["cool","lock","cook"]

Output: ["c","o"]

a부터 z를 카운트할 정수 배열로 풀려했지만....
입력 값 아래 같을 때 에러가 났다.

Input: ["acabcddd","bcbdbcbd","baddbadb","cbdddcac","aacbcccd","ccccddda","cababaab","addcaccd"]
Output: ["a","d","d","c","c"]

실패 코드

class Solution {
    public List<String> commonChars(String[] words) {
        List<String> list = new ArrayList<String>();
        int[] arr = new int[26];
        int longestStringIdx = 0;
        
        for (int i = 0; i < words.length; i++) {
            if (words[i].length() > longestStringIdx) {
                longestStringIdx = i;
            }
            
            for (int j = 0; j < words[i].length(); j++) {
                char character = words[i].charAt(j);
                arr[character - 'a']++;
            } 
        }
        
        for (int i = 0; i < words[longestStringIdx].length(); i++) {
            char character = words[longestStringIdx].charAt(i);
            
            if (arr[character - 'a'] >= words.length) {
                list.add(character + "");
                
                arr[character - 'a'] -= words.length;
            }
        }
        
        return list;
    }
}

결국 유튜브 보며 풀었다 ㅠㅠ 최솟값 함수, Math.min()로 풀 수 있는 문제를 헤맸다.


성공 코드

class Solution {
    public List<String> commonChars(String[] words) {
        List<String> commonChars = new ArrayList<String>();
        int alphabetLength = 26;
        int[] minCharCounts = new int[alphabetLength];
        
        Arrays.fill(minCharCounts, Integer.MAX_VALUE);
        
        for (String word : words) {
            int[] charCounts = new int[alphabetLength];
            
            for (char character : word.toCharArray()) {
                charCounts[character - 'a']++;
            }
            
            for (int i = 0; i < alphabetLength; i++) {
                minCharCounts[i] = Math.min(minCharCounts[i], charCounts[i]);
            }
        }
        
        for (int i = 0; i < alphabetLength; i++) {
            while (minCharCounts[i] > 0) {
                commonChars.add((char) (i + 'a') + "");
                minCharCounts[i]--;
            }
        }
        
        return commonChars;
    }
}

K = words 요소 중 가장 짧은 문자열 길이.

시간 복잡도: O(N x M)
공간 복잡도: O(K)


원리 설명
예시 1:
Input: words = ["bella","label","roller"]
Output: ["e","l","l"]

초기 minCharCounts (안 나온 값들은 MAX(정수 최댓값) 혹은 0, a와 z 제외).

a z
v v
[MAX] ... [MAX]


문자열 "bella" 순회 시.
"bella" 문자들 순회 이후 charCounts 값.
a b e l z
v v v v v
[1] [1] ... [1] ... [2] ... [0]

0부터 25까지 순회 시.
i = 0 일 때.
charCounts[0] = 1
minCharCounts[0] = Integer.MAX_VALUE
Math.min(1, Integer.MAX_VALUE)는 minCharCounts[0]에 1을 할당.

i = 1 일 때.
charCounts[1] = 1
minCharCounts[1] = Integer.MAX_VALUE
Math.min(1, Integer.MAX_VALUE)는 minCharCounts[1]에 1을 할당.

i = 4 일 때.
charCounts[4] = 1
minCharCounts[4] = Integer.MAX_VALUE
Math.min(1, Integer.MAX_VALUE)는 minCharCounts[4]에 1을 할당.

i = 11 일 때.
charCounts[11] = 2
minCharCounts[11] = Integer.MAX_VALUE
Math.min(2, Integer.MAX_VALUE)는 minCharCounts[11]에 2를 할당.

minCharCounts[0, 1, 4, 11 인덱스를 제외한 인덱스들] = 0
왜냐하면 charCounts의 다른 인덱스 값들은 0이고 minCharCounts의 Integer.MAX_VALUE보다 낮기때문.

문자열 "label" 순회 시.
"label" 문자들 순회 이후 charCounts 값.
a b e l z
v v v v v
[1] [1] ... [1] ... [2] ... [0]

0부터 25까지 순회 시.
i = 0 일 때.
charCounts[0] = 1
minCharCounts[0] = 1
Math.min(1, 1)는 minCharCounts[0]에 1을 할당.

i = 1 일 때.
charCounts[1] = 1
minCharCounts[1] = 1
Math.min(1, 1)는 minCharCounts[1]에 1을 할당.

i = 4 일 때.
charCounts[4] = 1
minCharCounts[4] = 1
Math.min(1, 1)는 minCharCounts[4]에 1을 할당.

i = 11 일 때.
charCounts[11] = 2
minCharCounts[11] = 2
Math.min(2, 2)는 minCharCounts[11]에 2를 할당.

minCharCounts[0, 1, 4, 11 인덱스를 제외한 인덱스들] = 0

문자열 "roller" 순회 시.
"roller" 문자들 순회 이후 charCounts 값.
a e l o r z
v v v v v v
[0] ... [1] ... [2] ... [1] ... [2] ... [0]

0부터 25까지 순회 시.
i = 4 일 때.
charCounts[4] = 1
minCharCounts[4] = 1
Math.min(1, 1)는 minCharCounts[4]에 1을 할당.

i = 11 일 때.
charCounts[11] = 2
minCharCounts[11] = 2
Math.min(2, 2)는 minCharCounts[11]에 2를 할당.

i = 14 일 때.
charCounts[14] = 1
minCharCounts[14] = 0
Math.min(1, 0)는 minCharCounts[14]에 0을 할당.

i = 17 일 때.
charCounts[17] = 2
minCharCounts[17] = 0
Math.min(2, 0)는 minCharCounts[17]에 0을 할당.

minCharCounts[4, 11 인덱스를 제외한 인덱스들] = 0


문자열 배열 순회 후.

a e l z
v v v v
[0] ... [1] ... [2] ... [0]


0부터 25까지 순회.
minCharCount[i]가 0보다 많을 시 순회.
i + 'a'를 문자열로 변환 후 commonChars에 추가.
minCharCount[i] 1 감소.

commonChars 반환.