LeetCode 솔루션

[5/11] 1641. Count Sorted Vowel Strings

mingki 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.05.10 17:27

11,219 조회
6 댓글
0 추천
0 비추천
목록 게시글 쓰기

[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 (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

#LeetCode, #Google, #Salesforce, #Amazon, #Dynamic Programming(DP)

링크

https://leetcode.com/problems/count-sorted-vowel-strings/ 3333 회 연결

익명
작성일 2022.05.11 00:27

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);        
    }
};

익명
작성일 2022.05.11 10:22

익명
작성일 2022.05.11 10:22

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

익명
작성일 2022.05.11 10:31

디스커션에서 굉장히 참신한 솔루션을 봐서 올려봅니다
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;
    }
};

익명
작성일 2022.05.11 11:31

조금 더 줄여봤습니다.

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;
    }
};

익명
작성일 2022.05.12 21:07

감사합니다.