1220. Count Vowels Permutation
Question
Given an integer
n
, your task is to count how many strings of lengthn
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.
Solution
DFS搜索,记忆化剪枝。
每次根据上一个字母last来从哈希表里选择下一个可选字母进行遍历,并计算总的可组成数sum。
Code
1 | class Solution { |
1220. Count Vowels Permutation
https://xuanhe95.github.io/2022/08/06/1220-Count-Vowels-Permutation/