1641. Count Sorted Vowel Strings

# 1641. Count Sorted Vowel Strings#

## 题目 #

Given an integer `n`, return the number of strings of length `n` that consist only of vowels (`a`, `e`*,* `i`*,* `o`*,* `u`*) and are **lexicographically sorted**.*

A string `s` is lexicographically sorted if for all valid `i``s[i]` is the same as or comes before `s[i+1]` in the alphabet.

Example 1:

``````Input: n = 1
Output: 5
Explanation: The 5 sorted strings that consist of vowels only are ["a","e","i","o","u"].
``````

Example 2:

``````Input: n = 2
Output: 15
Explanation: The 15 sorted strings that consist of vowels only are
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"].
Note that "ea" is not a valid string since 'e' comes after 'a' in the alphabet.

``````

Example 3:

``````Input: n = 33
Output: 66045

``````

Constraints:

• `1 <= n <= 50`

## 解题思路 #

• 题目给的数据量并不大，第一个思路是利用 DFS 遍历打表法。时间复杂度 O(1)，空间复杂度 O(1)。
• 第二个思路是利用数学中的组合公式计算结果。题目等价于假设现在有 n 个字母，要求取 4 次球（可以选择不取）将字母分为 5 堆，问有几种取法。确定了取法以后，`a``e``i``o``u`，每个字母的个数就确定了，据题意要求按照字母序排序，那么最终字符串也就确定了。现在关注解决这个组合问题就可以了。把问题再转化一次，等价于，有 n+4 个字母，取 4 次，问有几种取法。+4 代表 4 个空操作，取走它们意味着不取。根据组合的数学定义，答案为 C(n+4,4)。

## 代码 #

``````package leetcode

// 解法一 打表
func countVowelStrings(n int) int {
res := []int{1, 5, 15, 35, 70, 126, 210, 330, 495, 715, 1001, 1365, 1820, 2380, 3060, 3876, 4845, 5985, 7315, 8855, 10626, 12650, 14950, 17550, 20475, 23751, 27405, 31465, 35960, 40920, 46376, 52360, 58905, 66045, 73815, 82251, 91390, 101270, 111930, 123410, 135751, 148995, 163185, 178365, 194580, 211876, 230300, 249900, 270725, 292825, 316251}
return res[n]
}

func makeTable() []int {
res, array := 0, []int{}
for i := 0; i < 51; i++ {
countVowelStringsDFS(i, 0, []string{}, []string{"a", "e", "i", "o", "u"}, &res)
array = append(array, res)
res = 0
}
return array
}

func countVowelStringsDFS(n, index int, cur []string, vowels []string, res *int) {
vowels = vowels[index:]
if len(cur) == n {
(*res)++
return
}
for i := 0; i < len(vowels); i++ {
cur = append(cur, vowels[i])
countVowelStringsDFS(n, i, cur, vowels, res)
cur = cur[:len(cur)-1]
}
}

// 解法二 数学方法 —— 组合
func countVowelStrings1(n int) int {
return (n + 1) * (n + 2) * (n + 3) * (n + 4) / 24
}
``````

Apr 8, 2023
Edit this page