※ 引述《ZooseWu (动物园 公告)》之铭言：
: 1220. Count Vowels Permutation
: 给你一个n，表示字串的长度为n。
: 字串符合下面条件：
: - 每个字符只能是小写的 a e i o u
: - a 字符后面只能接 e
: - e 字符后面只能接 a 或 i
: - i 字符后面不能接 i
: - o 字符后面只能接 i 或 u
: - u 字符后面只能接 a
: 求所有字串可能的数量。
: input: 1 output: 5
: 所有可能: a e i o u
: input: 2 output: 10
: 所有可能: ae ea ei ia ie io iu oi ou ua
: input: 3 output: 68
: Approach:
: 这题要把题目的条件反过来
: - a 字符只能接在 e i u 后面
: - e 字符只能接在 a i 后面
: - i 字符只能接在 e o 后面
: - o 字符只能接在 i 后面
: - u 字符只能接在 i o 后面
: 然后我们只记录所有字串结尾是特定字符的数量
: 例如 n=2 的时候 a 有 ea ia ua ，所以 count.a = 3
: 然后每次进入下一轮 count.a = count.e + count.i + count.u
: TS code:
: function countVowelPermutation (n: number): number {
: const mod = 1000000007
: const count = { a: 1, e: 1, i: 1, o: 1, u: 1 }
: for (let i = 1; i < n; i++) {
: const prevCount = { ...count }
: count.a = (prevCount.e + prevCount.i + prevCount.u) % mod
: count.e = (prevCount.a + prevCount.i) % mod
: count.i = (prevCount.e + prevCount.o) % mod
: count.o = (prevCount.i) % mod
: count.u = (prevCount.i + prevCount.o) % mod
: }
: return Object.values(count).reduce((a, b) => a + b, 0) % mod
: }
: 我觉得这题蛮简单的，不知道为什么是hard
: 等等去偷看别人的答案看有没有我遗漏的或是更好的思路
Python Code:
class Solution:
def countVowelPermutation(self, n: int) -> int:
mod = 1000000007
a,e,i,o,u = 1,1,1,1,1
for j in range(1,n):
a_next = e % mod
e_next = (a+i) % mod
i_next = (a+e+o+u) %mod
o_next = (i+u) %mod
u_next = a % mod
a,e,i,o,u = a_next,e_next,i_next,o_next,u_next
return (a+e+i+o+u) % mod
想了很久直接看解答
不过我还是不太懂循环里面的规则
但对今天的问题有一些思路了
感谢动物园