[Algorithm] LeetCode - 1641. Count Sorted Vowel Strings(Dynamic Programming)

 

LeetCode 문제입니다.

[문제설명]

Given an integer n, return the number of strings of length n that consist only of vowels (a, e, i, o, u) and are lexicographically sorted.

A string s is lexicographically sorted if for all valid i, s[i] is the same as or comes before s[i+1] in the alphabet.

 

번역)

n이 주어졌을 때, 모음(a, e, i, o, u)로 구성되어 있고 정렬된 n 크기의 문자열 개수를 구하시오.
모든 유효한 i에 대해 s[i]가 알파벳에서 s[i+1]과 같거나 그 앞에 오는 경우 문자열 s는 사전순으로 정렬됩니다.

   -> 모음으로 구성된 문자열 s(크기는 n)의 경우의 수를 구하되, 사전 정렬순이어야한다.

 

 

Topic: Dynamic Programing

Level: Medium

Accepted 76,595 /Submissions 102,380

---

[제한사항]

• 1 <= n <= 50 

---

[입출력]

예시 1

Input: n = 1
Output: 5
Explanation: The 5 sorted strings that consist of vowels only are ["a","e","i","o","u"].

 

예시 2

 

Input: n = 2
Output: 15
Explanation: The 15 sorted strings that consist of vowels only are
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"].
Note that "ea" is not a valid string since 'e' comes after 'a' in the alphabet.

예시 3

Input: n = 33
Output: 66045

---

[문제풀이]

/**
 * @param {number} n
 * @return {number}
 */
var countVowelStrings = function(n) {
    // constraints 1
    if (n < 1 || n > 50 ) return false
    if (n === 1)  return 5 
    
    
    let result = 0
    const vowels = ["a","e","i","o","u"]
    
    const recursiveMatch = (num, lastVowel) => {
        // Finish making 
        if (num === n) return result++
        
        for (let i = vowels.indexOf(lastVowel); i < 5; i++) recursiveMatch(num + 1, vowels[i])    
        
    }
    

     recursiveMatch(1, "a")
     recursiveMatch(1, "e")
     recursiveMatch(1, "i")
     recursiveMatch(1, "o")
     recursiveMatch(1, "u")  
    
    return result
};

 

Idea: 

1. 각 vowel(모음)이 첫번째 alphabet인 경우를 나누어서 생각한다.

2. vowels는 모음이 정렬된 변수이다.

3. recursiveMatch 함수는 num번째 idx에 lastVowel(모음)을 input으로 하는 함수이다.

  -> num이 n이 되었을 경우엔 카운트를 한다. n번째에 lastVowel이 들어갔기 때문.

  -> lastVowel의 vowels idx부터 recursiveMatch함수를 n+1하여 재호출 한다.

      -> lastVowel과 같거나 후순서인 alphabet을 보장한다.

---

[Performance]