LeetCode 솔루션 분류
[8/7] 1220. Count Vowels Permutation
본문
Hard
2024139Add to ListShareGiven 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
태그
#C3 IoT
관련자료
-
링크
댓글 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.
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)
