题目描述
给你一个整数 n，请你帮忙统计一下我们可以按下述规则形成多少个长度为 n 的字符串：
- 字符串中的每个字符都应当是小写元音字母（
'a', 'e', 'i', 'o', 'u'）
- 每个元音
'a' 后面都只能跟着 'e'
- 每个元音
'e' 后面只能跟着 'a' 或者是 'i'
- 每个元音
'i' 后面 不能 再跟着另一个 'i'
- 每个元音
'o' 后面只能跟着 'i' 或者是 'u'
- 每个元音
'u' 后面只能跟着 'a'
由于答案可能会很大，所以请你返回 模 10^9 + 7 之后的结果。
示例 1：
输入：n = 1
输出：5
解释：所有可能的字符串分别是："a", "e", "i" , "o" 和 "u"。
示例 2：
输入：n = 2
输出：10
解释：所有可能的字符串分别是："ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" 和 "ua"。
示例 3：
输入：n = 5
输出：68
提示：
解法
方法一：动态规划
根据题目描述，我们先列出每个元音字母的后一个字母：
a [e]
e [a|i]
i [a|e|o|u]
o [i|u]
u [a]
那么我们可以推出每个元音字母的前一个字母：
[e|i|u] a
[a|i] e
[e|o] i
[i] o
[i|o] u
我们定义 $f[i]$ 表示当前长度以第 $i$ 个元音字母结尾的字符串的个数，如果长度为 $1$，那么 $f[i]=1$。
当长度大于 $1$ 时，我们定义 $g[i]$ 表示当前长度以第 $i$ 个元音字母结尾的字符串的个数，那么 $g[i]$ 可以由 $f$ 转移而来，即：
$$
g[i]=
\begin{cases}
f[1]+f[2]+f[4] & i=0 \
f[0]+f[2] & i=1 \
f[1]+f[3] & i=2 \
f[2] & i=3 \
f[2]+f[3] & i=4
\end{cases}
$$
最终答案为 $\sum_{i=0}^{4}f[i]$。注意由于答案可能会很大，所以需要对 $10^9+7$ 取模。
时间复杂度 $O(n)$，空间复杂度 $O(C)$。其中 $n$ 是字符串的长度，而 $C$ 是元音字母的个数。本题中 $C=5$。
1
2
3
4
5
6
7
8
9
10
11
12
13 | class Solution:
def countVowelPermutation(self, n: int) -> int:
f = [1] * 5
mod = 10**9 + 7
for _ in range(n - 1):
g = [0] * 5
g[0] = (f[1] + f[2] + f[4]) % mod
g[1] = (f[0] + f[2]) % mod
g[2] = (f[1] + f[3]) % mod
g[3] = f[2]
g[4] = (f[2] + f[3]) % mod
f = g
return sum(f) % mod
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | class Solution {
public int countVowelPermutation(int n) {
long[] f = new long[5];
Arrays.fill(f, 1);
final int mod = (int) 1e9 + 7;
for (int i = 1; i < n; ++i) {
long[] g = new long[5];
g[0] = (f[1] + f[2] + f[4]) % mod;
g[1] = (f[0] + f[2]) % mod;
g[2] = (f[1] + f[3]) % mod;
g[3] = f[2];
g[4] = (f[2] + f[3]) % mod;
f = g;
}
long ans = 0;
for (long x : f) {
ans = (ans + x) % mod;
}
return (int) ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | class Solution {
public:
int countVowelPermutation(int n) {
using ll = long long;
vector<ll> f(5, 1);
const int mod = 1e9 + 7;
for (int i = 1; i < n; ++i) {
vector<ll> g(5);
g[0] = (f[1] + f[2] + f[4]) % mod;
g[1] = (f[0] + f[2]) % mod;
g[2] = (f[1] + f[3]) % mod;
g[3] = f[2];
g[4] = (f[2] + f[3]) % mod;
f = move(g);
}
return accumulate(f.begin(), f.end(), 0LL) % mod;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | func countVowelPermutation(n int) (ans int) {
const mod int = 1e9 + 7
f := make([]int, 5)
for i := range f {
f[i] = 1
}
for i := 1; i < n; i++ {
g := make([]int, 5)
g[0] = (f[1] + f[2] + f[4]) % mod
g[1] = (f[0] + f[2]) % mod
g[2] = (f[1] + f[3]) % mod
g[3] = f[2] % mod
g[4] = (f[2] + f[3]) % mod
f = g
}
for _, x := range f {
ans = (ans + x) % mod
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | function countVowelPermutation(n: number): number {
const f: number[] = Array(5).fill(1);
const mod = 1e9 + 7;
for (let i = 1; i < n; ++i) {
const g: number[] = Array(5).fill(0);
g[0] = (f[1] + f[2] + f[4]) % mod;
g[1] = (f[0] + f[2]) % mod;
g[2] = (f[1] + f[3]) % mod;
g[3] = f[2];
g[4] = (f[2] + f[3]) % mod;
f.splice(0, 5, ...g);
}
return f.reduce((a, b) => (a + b) % mod);
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | /**
* @param {number} n
* @return {number}
*/
var countVowelPermutation = function (n) {
const mod = 1e9 + 7;
const f = Array(5).fill(1);
for (let i = 1; i < n; ++i) {
const g = Array(5).fill(0);
g[0] = (f[1] + f[2] + f[4]) % mod;
g[1] = (f[0] + f[2]) % mod;
g[2] = (f[1] + f[3]) % mod;
g[3] = f[2];
g[4] = (f[2] + f[3]) % mod;
f.splice(0, 5, ...g);
}
return f.reduce((a, b) => (a + b) % mod);
};
|
方法二：矩阵快速幂加速递推
时间复杂度 $O(C^3 \times \log n)$，空间复杂度 $O(C^2)$，其中 $C$ 是元音字母的个数，本题中 $C=5$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | import numpy as np
class Solution:
def countVowelPermutation(self, n: int) -> int:
mod = 10**9 + 7
factor = np.asmatrix(
[
(0, 1, 0, 0, 0),
(1, 0, 1, 0, 0),
(1, 1, 0, 1, 1),
(0, 0, 1, 0, 1),
(1, 0, 0, 0, 0),
],
np.dtype("O"),
)
res = np.asmatrix([(1, 1, 1, 1, 1)], np.dtype("O"))
n -= 1
while n:
if n & 1:
res = res * factor % mod
factor = factor * factor % mod
n >>= 1
return res.sum() % mod
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40 | class Solution {
private final int mod = (int) 1e9 + 7;
public int countVowelPermutation(int n) {
long[][] a
= {{0, 1, 0, 0, 0}, {1, 0, 1, 0, 0}, {1, 1, 0, 1, 1}, {0, 0, 1, 0, 1}, {1, 0, 0, 0, 0}};
long[][] res = pow(a, n - 1);
long ans = 0;
for (long x : res[0]) {
ans = (ans + x) % mod;
}
return (int) ans;
}
private long[][] mul(long[][] a, long[][] b) {
int m = a.length, n = b[0].length;
long[][] c = new long[m][n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
for (int k = 0; k < b.length; ++k) {
c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;
}
}
}
return c;
}
private long[][] pow(long[][] a, int n) {
long[][] res = new long[1][a.length];
Arrays.fill(res[0], 1);
while (n > 0) {
if ((n & 1) == 1) {
res = mul(res, a);
}
a = mul(a, a);
n >>= 1;
}
return res;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43 | class Solution {
public:
int countVowelPermutation(int n) {
vector<vector<ll>> a = {
{0, 1, 0, 0, 0},
{1, 0, 1, 0, 0},
{1, 1, 0, 1, 1},
{0, 0, 1, 0, 1},
{1, 0, 0, 0, 0}};
vector<vector<ll>> res = pow(a, n - 1);
return accumulate(res[0].begin(), res[0].end(), 0LL) % mod;
}
private:
using ll = long long;
const int mod = 1e9 + 7;
vector<vector<ll>> mul(vector<vector<ll>>& a, vector<vector<ll>>& b) {
int m = a.size(), n = b[0].size();
vector<vector<ll>> c(m, vector<ll>(n));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
for (int k = 0; k < b.size(); ++k) {
c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;
}
}
}
return c;
}
vector<vector<ll>> pow(vector<vector<ll>>& a, int n) {
vector<vector<ll>> res;
res.push_back({1, 1, 1, 1, 1});
while (n) {
if (n & 1) {
res = mul(res, a);
}
a = mul(a, a);
n >>= 1;
}
return res;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43 | const mod = 1e9 + 7
func countVowelPermutation(n int) (ans int) {
a := [][]int{
{0, 1, 0, 0, 0},
{1, 0, 1, 0, 0},
{1, 1, 0, 1, 1},
{0, 0, 1, 0, 1},
{1, 0, 0, 0, 0}}
res := pow(a, n-1)
for _, x := range res[0] {
ans = (ans + x) % mod
}
return
}
func mul(a, b [][]int) [][]int {
m, n := len(a), len(b[0])
c := make([][]int, m)
for i := range c {
c[i] = make([]int, n)
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
for k := 0; k < len(b); k++ {
c[i][j] = (c[i][j] + a[i][k]*b[k][j]) % mod
}
}
}
return c
}
func pow(a [][]int, n int) [][]int {
res := [][]int{{1, 1, 1, 1, 1}}
for n > 0 {
if n&1 == 1 {
res = mul(res, a)
}
a = mul(a, a)
n >>= 1
}
return res
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39 | const mod = 1e9 + 7;
function countVowelPermutation(n: number): number {
const a: number[][] = [
[0, 1, 0, 0, 0],
[1, 0, 1, 0, 0],
[1, 1, 0, 1, 1],
[0, 0, 1, 0, 1],
[1, 0, 0, 0, 0],
];
const res = pow(a, n - 1);
return res[0].reduce((a, b) => (a + b) % mod);
}
function mul(a: number[][], b: number[][]): number[][] {
const [m, n] = [a.length, b[0].length];
const c = Array.from({ length: m }, () => Array.from({ length: n }, () => 0));
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
for (let k = 0; k < b.length; ++k) {
c[i][j] =
(c[i][j] + Number((BigInt(a[i][k]) * BigInt(b[k][j])) % BigInt(mod))) % mod;
}
}
}
return c;
}
function pow(a: number[][], n: number): number[][] {
let res: number[][] = [[1, 1, 1, 1, 1]];
while (n) {
if (n & 1) {
res = mul(res, a);
}
a = mul(a, a);
n >>>= 1;
}
return res;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44 | /**
* @param {number} n
* @return {number}
*/
const mod = 1e9 + 7;
var countVowelPermutation = function (n) {
const a = [
[0, 1, 0, 0, 0],
[1, 0, 1, 0, 0],
[1, 1, 0, 1, 1],
[0, 0, 1, 0, 1],
[1, 0, 0, 0, 0],
];
const res = pow(a, n - 1);
return res[0].reduce((a, b) => (a + b) % mod);
};
function mul(a, b) {
const [m, n] = [a.length, b[0].length];
const c = Array.from({ length: m }, () => Array.from({ length: n }, () => 0));
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
for (let k = 0; k < b.length; ++k) {
c[i][j] =
(c[i][j] + Number((BigInt(a[i][k]) * BigInt(b[k][j])) % BigInt(mod))) % mod;
}
}
}
return c;
}
function pow(a, n) {
let res = [[1, 1, 1, 1, 1]];
while (n) {
if (n & 1) {
res = mul(res, a);
}
a = mul(a, a);
n >>>= 1;
}
return res;
}
|