문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

문자열 licensePlate와 문자열 배열 words이 주어졌을 때, 배열을 완성하는 가장 짧은 단어를 찾아라.

완성 단어는 licensePlate에 있는 모든 글자를 포함하는 단어이다. licensePlate에서 숫자와 공백은 무시하고, 글자는 대소문자를 구분하지 않는다. licensePlate에 같은 글자가 두 번 이상 나타나면, 완성 단어에도 같은 횟수 이상 나타나야 한다.

예를 들어, licensePlate = "aBc 12c"라면, 'a', 'b', 'c'가 두 번 포함되어 있다. 가능한 완성 단어로는 "abccdef", "caaacab", "cbca"등이 있다.

단어의 개수를 세어 가장 짧은 완성 단어를 반환해라. 정답은 반드시 존재한다. 가장 짧은 완성 단어가 여러 개인 경우, 단어의 개수를 세어 가장 먼저 나타나는 단어를 반환해라.

Example

#1
Input: licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"]
Output: "steps"
Explanation: licensePlate는 문자 's', 'p', 's','t'가 포함된다.
"step"은 't'와 'p'를 포함하지만, 오직 1개의 's'를 포함한다.
"steps"는 't', 'p'와 두 개의 's'를 포함한다.
"stripe"는 하나의 's'를 놓쳤다.
"stepple"은 하나의 's'를 놓쳤다.
따라서 "steps"는 모든 문자를 포함한 단어이다.

#2
Input: licensePlate = "1s3 456", words = ["looks", "pest", "stew", "show"]
Output: "pest"
Explanation: licensePlate는 오직 문자 's'만 포함한다. 모든 단어들은 's'를 포함하고 있지만, 그 중에 "pest", "stew", "show"가 가장 짧다. "pest"가 세 단어 중 가장 먼저 나오는 단어라서 정답이다.

Constraints

• 1 <= licensePlate.length <= 7
• licensePlate는 숫자, 문자, 공백이 포함된다.
• 1 <= words.length <= 1000
• 1 <= words[i].length <= 15
• words[i]는 소문자 영어로 구성된다.

Solved

class Solution {
    public String shortestCompletingWord(String licensePlate, String[] words) {
        int[] required = new int[26];
        
        for (char c : licensePlate.toCharArray()) {
            if (Character.isLetter(c)) {
                required[Character.toLowerCase(c) - 'a']++;
            }
        }
        
        String result = null;
        
        for (String word : words) {
            
            int[] freq = new int[26];
            
            for (char c : word.toCharArray()) {
                freq[c - 'a']++;
            }
            
            if (matches(required, freq)) {
                if (result == null || word.length() < result.length()) {
                    result = word;
                }
            }
        }
        
        return result;
    }
    
    private boolean matches(int[] required, int[] freq) {
        for (int i = 0; i < 26; i++) {
            if (freq[i] < required[i]) {
                return false;
            }
        }
        return true;
    }
}