题目大意：
统计元音字母序列的数目
给你一个整数 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
提示：
1 <= n <= 2 * 10^4
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1220
解题思路分析：
虽然这是一道Hard级别的题目，但是如果把思路屡清了，其实并没有太大的难度。我们总结一下每个字母的后续连接可能：
a: [e]; e: [a, i]; i: [a, e, o, u]; o: [i, u]; u: [a];
反过来，每个字母的前序连接可能为：
a: [e, i, u]; // 上层一共有多少e, i和u，本层就会出现多少a e: [a, i]; // 上层一共有多少a和i，本层就会出现多少e i: [e, o]; o: [i]; u: [i, o];
知道了上面这两个关系，我们可以将这道题想象成一个树结构，树的所有分支即是答案。比如当树的高度为1时，有5个分支分别为a，e，i，o，u。
当高度为2时：
- a下面有1个分支e
- e下面有2个分支a和i
- i下面有4个分支a，e，o，u
- o下面有2个分支i，u
- u下面有1个分支a
一共是10个分支，分别为3个a，2个e，2个i，1个0，2个u。
当高度为3时，与高度2时的处理类似：
- a下面有1个分支e，此时有3个a因此有3个分支e
- e下面有2个分支a和i，此时有2个e，因此分别有2个分支a和i
- i下面有4个分支a，e，o，u，此时有2个i，因此分别有2个分支a，e，o，u
- o下面有2个分支i和u，此时有1个o，因此有1个分支i和1个分支u
- u下面有1个分支a，此时有2个u，因此有2个分支a
一共是19个分支。
上面就是基本的编程思路，首先我们先统计当前层分别有多少个a，e，i，o，u。他们的总和即是当层的结果。然后到下一层，分别看他们能出现多少分支，再统计出各个字母的个数，以此类推，直到循环至第n层结束。
看下完整实现代码：
public int countVowelPermutation(int n) {
long a=1,e=1,i=1,o=1,u=1; // 每个字母初始个数为1
while(n-->1){ // 循环n-1次
long countA = (e+i+u) % 1000000007; // 当层能出现多少a
long countE = (a+i) % 1000000007; // 当层能出现多少e
long countI = (e+o) % 1000000007; // 当层能出现多少i
long countO = i % 1000000007; // 当层能出现多少o
long countU = (i+o) % 1000000007; // 当层能出现多少u
a = countA; // 更新a的个数
e = countE; // 更新e的个数
i = countI; // 更新i的个数
o = countO; // 更新o的个数
u = countU; // 更新u的个数
}
return (int)((a+e+i+o+u) % 1000000007); // 返回5个字母个数总和
} 本题解法执行时间为7ms。
Runtime: 7 ms, faster than 88.56% of Java online submissions for Count Vowels Permutation.
Memory Usage: 33 MB, less than 100.00% of Java online submissions for Count Vowels Permutation.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1220-count-vowels-permutation-解题思路分析/