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 ListShareGiven 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
관련자료
-
링크
댓글 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.
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);
}
};
나무토끼님의 댓글
- 익명
- 작성일
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.
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 ansmingki님의 댓글
- 익명
- 작성일
디스커션에서 굉장히 참신한 솔루션을 봐서 올려봅니다
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.
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;
}
};
