[리트코드] 809. Expressive Words / Javascript

문제주소 : https://leetcode.com/problems/expressive-words/

Expressive Words - LeetCode

---

<문제 설명>

Sometimes people repeat letters to represent extra feeling. For example:

• "hello" -> "heeellooo"
• "hi" -> "hiiii"

In these strings like "heeellooo", we have groups of adjacent letters that are all the same: "h", "eee", "ll", "ooo".

You are given a string s and an array of query strings words. A query word is stretchy if it can be made to be equal to s by any number of applications of the following extension operation: choose a group consisting of characters c, and add some number of characters c to the group so that the size of the group is three or more.

• For example, starting with "hello", we could do an extension on the group "o" to get "hellooo", but we cannot get "helloo" since the group "oo" has a size less than three. Also, we could do another extension like "ll" -> "lllll" to get "helllllooo". If s = "helllllooo", then the query word "hello" would be stretchy because of these two extension operations: query = "hello" -> "hellooo" -> "helllllooo" = s.

Return the number of query strings that are stretchy.

 

Example 1:

Input: s = "heeellooo", words = ["hello", "hi", "helo"] Output: 1 Explanation: We can extend "e" and "o" in the word "hello" to get "heeellooo". We can't extend "helo" to get "heeellooo" because the group "ll" is not size 3 or more.

Example 2:

Input: s = "zzzzzyyyyy", words = ["zzyy","zy","zyy"] Output: 3

 

Constraints:

• 1 <= s.length, words.length <= 100
• 1 <= words[i].length <= 100
• s and words[i] consist of lowercase letters.

 

<풀이법>

▒ 한줄 개념: 구현 ▒ 

특별히 어떤 알고리즘을 사용해야하는 문제라기보다는, 각 단어들을 적절하게 dictionary화 해서 비교하면 되는 문제입니다.

 

제가 문제에서 구현한 딕셔너리의 형태는 다음과 같습니다.

word = 'heeellooo'
-> dict = [['h', 1], ['e', 3], ['l', 2], ['o', 3]]

 

풀이방법은 다음과 같습니다.

1. s에 대한 딕셔너리 (s_dict) 생성

2. words 배열의 원소들에 대해 반복문을 진행하며, answer 값 증가

  2-1. word에 대한 딕셔너리 (word_dict) 생성

  2-2. s_dict, word_dict를 비교하여 stretchy 여부 판단

    2-2-1. s_dict[i]의 char !== word_dict[i]의 char 일 경우, not stretchy

            (ex: s_dict[i] = ['h', 1], word_dict[i] = ['e', 0])

    2-2-2. s_dict[i]의 count < word_dict[i]의 count 일 경우, not stretchy

            (ex: s_dict[i] = ['h', 1], word_dict[i] = ['h', 3])

    2-2-3. s_dict[i]의 count !== word_dict[i]의 count && s_dict[count] < 3 일 경우, not stretchy

            (ex: s_dict[i] = ['h', 2], word_dict[i] = ['h', 1])

    2-2-4. 위 조건문을 모두 통과하였을 경우, stretchy

3. answer 값 return

 

<코드(Javascript)>

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number}
 */
var expressiveWords = function(s, words) {
    const makeDict = word => {
        const splitted = word.split('');
        const dict = [];
        let prev_char = '';
        splitted.map(char => {
            if(char !== prev_char){
                dict.push([char, 1]);
                prev_char = char;
            }else{
                dict[dict.length - 1][1]++;
            }
        })
        return dict;
    }
    
    const s_dict = makeDict(s);
    
    return words.reduce((count, word) => {
        const word_dict = makeDict(word);
        if(word_dict.length !== s_dict.length) return count;
        else{
            for(let i = 0; i < word_dict.length; i++){
                const [w_char, w_count] = word_dict[i];
                const [s_char, s_count] = s_dict[i];
                if(w_char !== s_char) return count;
                if(w_count > s_count) return count;
                if(w_count !== s_count && s_count < 3) return count;
            }
            return count+1;
        }
    }, 0);
};

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest