엔지니어 게시판
LeetCode 솔루션 분류

[8/7] 1220. Count Vowels Permutation

컨텐츠 정보

본문

Hard
2024139Add to ListShare

Given an integer n, your task is to count how many strings of length n can be formed under the following rules:

  • Each character is a lower case vowel ('a''e''i''o''u')
  • Each vowel 'a' may only be followed by an 'e'.
  • Each vowel 'e' may only be followed by an 'a' or an 'i'.
  • Each vowel 'i' may not be followed by another 'i'.
  • Each vowel 'o' may only be followed by an 'i' or a 'u'.
  • Each vowel 'u' may only be followed by an 'a'.

Since the answer may be too large, return it modulo 10^9 + 7.

 

Example 1:

Input: n = 1
Output: 5
Explanation: All possible strings are: "a", "e", "i" , "o" and "u".

Example 2:

Input: n = 2
Output: 10
Explanation: All possible strings are: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua".

Example 3: 

Input: n = 5
Output: 68

 

Constraints:

  • 1 <= n <= 2 * 10^4
Accepted
81,638
Submissions
135,649
태그

관련자료

댓글 1

학부유학생님의 댓글

  • 익명
  • 작성일
Runtime: 909 ms, faster than 37.56% of Python3 online submissions for Count Vowels Permutation.
Memory Usage: 14.3 MB, less than 59.48% of Python3 online submissions for Count Vowels Permutation.

import collections
class Solution:
    def countVowelPermutation(self, n: int) -> int:
        dic = {
            "a":['e'],
            'e':['a','i'],
            'i':['a','e','o','u'],
            'o':['i','u'],
            'u':['a']
        }
        prev_counter = {"a":1, "e":1,"i":1,"o":1,"u":1}
        
        
        for _ in range(n-1):
            curr_counter = collections.defaultdict(int)
            for key, freq in prev_counter.items():
                for char in dic[key]:
                    curr_counter[char] += freq
            prev_counter = curr_counter
        
        res = 0
        
        for key, val in prev_counter.items():
            res += val
        
        return res % (10**9+7)
전체 396 / 1 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


알림 0