[LeetCode] 748. Shortest Completing Word

출처: leetcode.com/problems/shortest-completing-word/

Shortest Completing Word - LeetCode

문제

문자열 licensePlate와 문자열 배열 words가 주어질 때, words에서 가장 짧고 완성된(completing) 단어를 찾아라.

 

완성된 단어는 licensePlate의 모든 문자를 포함하고 있는 단어를 말한다. lincensePlate의 숫자와 공백은 무시하고, 대소문자를 구분하지 않고 문자를 처리해야 한다. 만약 문자가 lincensePlate에서 한번 이상 등장한다면, 단어 내에서도 동일한 횟수만큼 등장해야 한다.

 

예를 들어, lincensePlate = "aBc 12c"이면, 이 문자열는 a, b, 그리고 두개의 c를 포함한다. 가능한 완성된 문자는 "abccdef", "caaacab", 그리고 "cbca"이다.

 

words에서 가장 짧고 완성된 단어를 반환하라. 답의 존재가 보장된다. 가장 짧고 완성된 단어가 여러 개일 경우, words에서 먼저 발견되는 한 단어를 반환하라.

예제

Input: licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"]
Output: "steps"

Explanation: licensePlate contains letters 's', 'p', 's' (ignoring case), and 't'.
"step" contains 't' and 'p', but only contains 1 's'.
"steps" contains 't', 'p', and both 's' characters.
"stripe" is missing an 's'.
"stepple" is missing an 's'.
Since "steps" is the only word containing all the letters, that is the answer.

풀이

lincensePlate에는 completing 단어를 찾는데 불필요한 문자들이 포함되어 있기 때문에 이를 없애는 작업을 우선적으로 수행하였다.

licensePlate = licensePlate.replace(/\d|\s/g, '').toLowerCase();

정규표현식을 통해서 숫자 또는 공백을 찾아 빈 문자와 치환을 수행하였다.

 

이후, 정제된 licensePlate에서 각 문자가 몇 번 나오는지 쉽게 알기위해서 {key: letter, val: count of letter} 형식으로 만든다. licensePlate에 대해 수행한 작업의 예시이다.

licensePlate = "1s3 PSt"

1) licensePlate의 정제 과정을 거친 후, licensePlate = "spst"
2) Map 구조로 licensePlate를 구조화
letters = [
  {key: s, val: 2},
  {key: p, val: 1},
  {key: t, val: 1}
]

아래는 위 과정을 코드화한 것이다.

letters = new Map();
for (let letter of licensePlate){
    if (!letters.has(letter)) { letters.set(letter, 0); }
    letters.set(letter, letters.get(letter) +1);
}

이제 words의 각 word 또한 각 단어의 구성 문자를 파악하기 위해서 {key: letter, val: count of letter} 형식으로 만들어 준다.

words.map(word => {
    const word_letters = new Map();
    for (let letter of word){
        if (!word_letters.has(letter)) { word_letters.set(letter, 0); }
        word_letters.set(letter, letters.get(letter) +1);
    }
});

현재까지 과정을 통해서 licensePlate와 words의 각 word가 어떤 문자들로 구성되어 있는지 분해를 해놨기 때문에 licensePlate의 구성 요소를 word가 완전히 갖고 있는지 아닌지를 아래와 같이 판단할 수 있다.

letters = [{key: s, val: 2}, {key: p, val: 1}, {key: t, val: 1}]
=========================================================================================
word = "steps"
word_letters = [{key: s, val: 2}, {key: t, val: 1}, {key: e, val: 1}, {key: p, val: 1}]

1) `s`가 word_letters에 있는가? Yes
    1-1) `s`가 word_letters에 2개이상 있는가? Yes
2) `p`가 word_letters에 있는가? Yes
    2-1) `p`가 word_letters에 1개이상 있는가? Yes
3) `t`가 word_letters에 있는가? Yes
    2-1) `t`가 word_letters에 1개이상 있는가? Yes

=> "steps"는 completing한 문자이다.
=========================================================================================
word = "step"
word_letters = [{key: s, val: 1}, {key: t, val: 1}, {key: e, val: 1}, {key: p, val: 1}]
1) `s`가 word_letters에 있는가? No!

=> "step"은 completing한 문자가 아니다.

이 과정을 코드로 표현하면 아래와 같으며, 최종 목표가 completing하면서 가장 짧은 단어를 찾는 것이므로 길이 비교를 통해 answer에는 현재까지 알고 있는 completing한 단어 중 가장 짧은 단어만이 저장되도록 하였다.

let answer = '';
words.map(word => {
    const word_letters = new Map();
    for (let letter of word){
        if (!word_letters.has(letter)) { word_letters.set(letter, 0); }
        word_letters.set(letter, letters.get(letter) +1);

        for (let [letter, count] of letters) {
            if (!word_letters.has(letter) || word_letters.get(letter) < count) { reutrn; }
        }

        answer = !answer ? word : answer.length > word.length ? word : answer;
    }
});

 

Github: 748.js

opwe37/Algorithm-Study