LeetCode 솔루션 분류

[5/11] 1641. Count Sorted Vowel Strings

컨텐츠 정보

본문

[LeetCode 시즌 3] 2022년 5월 11일 문제입니다.

https://leetcode.com/problems/count-sorted-vowel-strings/


1641. Count Sorted Vowel Strings
Medium
179939Add to ListShare

Given an integer n, return the number of strings of length n that consist only of vowels (aeiou) and are lexicographically sorted.

A string s is lexicographically sorted if for all valid is[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 

관련자료

댓글 6

austin님의 댓글

  • 익명
  • 작성일
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Count Sorted Vowel Strings.
Memory Usage: 6 MB, less than 34.92% of C++ online submissions for Count Sorted Vowel Strings.
class Solution {
public:
    int countVowelStrings(int n) {
        vector<int> m(5, 1);
        for(auto i = 1; i < n; ++i) for(auto j = 4; j >= 0; --j) for(auto k = 0; k < j; ++k) m[j] += m[k];
        return accumulate(m.begin(), m.end(), 0);        
    }
};

mingki님의 댓글

  • 익명
  • 작성일

나무토끼님의 댓글

  • 익명
  • 작성일
Runtime: 5922 ms, faster than 7.88% of Python3 online submissions for Count Sorted Vowel Strings.
Memory Usage: 14 MB, less than 27.45% of Python3 online submissions for Count Sorted Vowel Strings.
class Solution:
    def countVowelStrings(self, n: int) -> int:
        ans = 0
        def backtracking(idx, cnt, n):
            nonlocal ans
            if cnt == n:
                ans += 1
                return
            
            for i in range(idx, 5):
                backtracking(i, cnt + 1, n)
        backtracking(0, 0, n)
        return ans

mingki님의 댓글

  • 익명
  • 작성일
디스커션에서 굉장히 참신한 솔루션을 봐서 올려봅니다
C++
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Count Sorted Vowel Strings.
Memory Usage: 5.8 MB, less than 85.48% of C++ online submissions for Count Sorted Vowel Strings.
class Solution {
public:
    int countVowelStrings(int n) {
        int a=1, e=1, i=1, o=1, u=1;
        
        while(--n){
            o += u;
            i += o;
            e += i;
            a += e;
        }
        return a+e+i+o+u;
    }
};

austin님의 댓글의 댓글

  • 익명
  • 작성일
조금 더 줄여봤습니다.
class Solution {
public:
    int countVowelStrings(int n) {
        int a=0, e=0;
        for(auto i = 1; i <= n; ++i) {
            e += i*i + i;
            a += e;
        }
        return (a+e+n+n*n)/2+n+1;
    }
};
LeetCode 솔루션 357 / 13 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


알림 0