输入n个字符串字典序排序_leetcode1641_go_统计字典序元音字符串的数目

题目

给你一个整数 n，请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。

字符串 s 按 字典序排列 需要满足：对于所有有效的 i，

s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。

示例 1：输入：n = 1 输出：5

解释：仅由元音组成的 5 个字典序字符串为 ["a","e","i","o","u"]

示例 2：输入：n = 2 输出：15

解释：仅由元音组成的 15 个字典序字符串为

["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]

注意，"ea" 不是符合题意的字符串，因为 'e' 在字母表中的位置比 'a' 靠后

示例 3：输入：n = 33 输出：66045

提示：1 <= n <= 50

解题思路分析

1、动态规划；时间复杂度O(n^2)，空间复杂度O(n)

func countVowelStrings(n int) int {dp := make([][5]int, n+1)dp[0][0], dp[0][1], dp[0][2], dp[0][3], dp[0][4] = 1, 1, 1, 1, 1for i := 1; i <= n; i++ {for j := 0; j < 5; j++ {for k := 0; k <= j; k++ {dp[i][j] = dp[i][j] + dp[i-1][k]}}}res := 0for i := 0; i < 5; i++ {res = res + dp[n-1][i]}return res}

2、动态规划；时间复杂度O(n)，空间复杂度O(1)

func countVowelStrings(n int) int {dp := make([]int, 5)dp[0] = 1for i := 0; i < n; i++ {for j := 1; j < 5; j++ {dp[j] = dp[j] + dp[j-1]}}res := 0for i := 0; i < 5; i++ {res = res + dp[i]}return res}

3、数学；时间复杂度O(1)，空间复杂度O(1)

// 将n个小球放到m个盒子里，盒子可以空：C(n+m-1, m-1) m=5 => C(n+4,4)// 在n+4中选择4个整数(4*3*2)func countVowelStrings(n int) int {return (n + 4) * (n + 3) * (n + 2) * (n + 1) / 24}

总结

Medium题目，可以使用动态规划，也可以使用数学进行分析