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

# [8/7] 1220. Count Vowels Permutation

• 작성
• 작성일

• 1,449 조회
• 1 댓글
• 0 추천
• 0 비추천

### 본문

Hard

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)``````
전체 380 / 1 페이지

• 등록일 11:10
• 등록일 09.28
• 등록일 09.27
• 등록일 09.27
• 등록일 09.27
• 등록일 09.27
• 등록일 09.26
• 등록일 09.26

• 등록일 08.22
• 등록일 09.07
• 등록일 09.07
• 등록일 09.08
• 등록일 09.08
• 등록일 09.08
• 등록일 09.08
• 등록일 09.09

• 등록일 09.27
• 등록일 09.26
• 등록일 09.26
• 등록일 09.23
• 등록일 09.22

### Stats

• 현재 접속자 254 명
• 오늘 방문자 4,976 명
• 어제 방문자 5,872 명
• 최대 방문자 6,163 명
• 전체 회원수 768 명