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
等等去偷看别人的答案看有没有我遗漏的或是更好的思路