Portfolio

문제

1641. Count Sorted Vowel Strings

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.

Example 1:


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

Example 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.

Example 3:


Input: n = 33
Output: 66045

Constraints:

1 <= n <= 50

풀이

은찬


var countVowelStrings = function(n) {
    let answer = 0;
    const dp = Array(5).fill(1);
    
    for(let i = 1; i < n; i++){
        for(let j = 0; j < 5; j++){
            for(let k = j + 1; k < 5; k++){
                dp[j] += dp[k];
            }
        }
    }
    
    return dp.reduce((acc, curr) => acc += curr, 0);
};

효성

규칙이 찾아질 듯 말듯해서 포기안하려다 결국 답 봤습니다 디피 으으 어렵네여


let res = 0
    
    helper(n, 0)

    function helper(n, startIdx) { 
        // base case
        if (n === 0) {
            res++
            return
        }

        // recursive case
        for (let i = startIdx; i < 5; i++) {
            helper(n - 1, i)
        }
    }

    return res

재영


const countVowelStrings = (n) => {
  const arr = Array.from({ length: n }, () => new Array(5).fill(0)); 
	// 2차원 배열
 // a -> a e i o u  // e -> e i o u // ...
(다음 행에서의 특정 인덱스 값) = (이전 행에서의 특정 인덱스 값) + (이전 행에서의 특정 인덱스 값보다 높은? 애들)
  for (let i = 0; i < n; i += 1) { // 1 ~ n까지
    for (let j = 0; j < 5; j += 1) { // a e i o u
      if (!i) { // 0이면 초기화할 때 자기자신
        arr[i][j] = 1;
      } else {
        for (let k = 0; k <= j; k += 1) { // 자신과 같거나 더 높은 애들
          arr[i][j] += arr[i - 1][k];
        }
      }
    }
  }

  return arr[arr.length - 1].reduce((acc, cur) => acc + cur, 0);
};