LeetCode-Go 题解 | 1641. Count Sorted Vowel Strings：字典序元音串计数的 DFS 打表与组合数学法

LeetCode-Go 题解 | 1641. Count Sorted Vowel Strings：字典序元音串计数的 DFS 打表与组合数学法

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本文是 LeetCode-Go 仓库对 LeetCode 第 1641 题《Count Sorted Vowel Strings》的完整解题笔记。文章以 leetcode/1641.Count-Sorted-Vowel-Strings/README.md 为骨架，逐层剖析题目语义、DFS 回溯枚举、打表预处理与组合数学公式 C(n+4,4) 两条核心思路，并结合仓库内的 Go 实现 与 单元测试 验证每一处推导。读完本文，你将掌握「重复组合（multiset combination）」建模技巧，并能独立写出 O(1) 复杂度的极简解法。

题目回顾

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

字符串s按字典序排列，指的是对于所有合法的下标i，s[i]在字母表中的位置总是与s[i+1]相同，或位于s[i+1]之前。换言之，元音字符在字符串内部必须非降序出现。

示例

示例 1：

Input: n = 1 Output: 5 Explanation: 仅由元音组成的 5 个有序字符串为 ["a","e","i","o","u"]。

示例 2：

Input: n = 2 Output: 15 Explanation: 仅由元音组成且有序的 15 个字符串为 ["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]。 注意 "ea" 不是合法字符串，因为 'e' 在字母表中位于 'a' 之后。

示例 3：

Input: n = 33 Output: 66045

约束条件

• 1 <= n <= 50

原文档给出的数据范围很小（n最大只有 50），这意味着暴力枚举在理论上是可行的，也为后面「打表」解法提供了前提。不过我们依然可以找到 O(1) 的纯数学解法，这也是本题的精髓所在。

解题思路一：DFS 回溯枚举 + 打表

原文档指出：题目给的数据量并不大，第一个思路是利用 DFS 遍历打表法。这样做的时间复杂度为 O(1)，空间复杂度为 O(1)（打表完成后的单次查询）。

回溯生成所有非降序元音串

关键在于保证生成出的字符串天然满足字典序要求：每一次递归只能从「当前字符及其之后」的元音集合中选取下一个字符，这样后一个字符永远不会小于前一个字符。

仓库源码中的countVowelStringsDFS正是这样实现的（见 1641. Count Sorted Vowel Strings.go）：

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] } }

逐行拆解这段回溯逻辑：

1. vowels = vowels[index:]：把可选元音集合收缩为「从index开始的子集」，index正是上一层递归选中的字符位置，从而保证非降序；
2. if len(cur) == n：当前已拼接满n个字符，说明找到一条合法路径，计数器res加一后返回；
3. 循环内countVowelStringsDFS(n, i, cur, vowels, res)传入i作为新的index，使得下一层只能选不小于当前字符的元音；
4. cur = cur[:len(cur)-1]是经典的回溯「还原现场」操作，将刚追加的字符弹出，以便尝试下一种选择。

例如n = 2时，DFS 会依次枚举出aa, ae, ai, ao, au, ee, ei, ...，与题目示例 2 给出的 15 个结果完全一致，而ea这类逆序串永远不会出现。

打表：把暴力结果固化为常量表

如果每次请求都重新 DFS 枚举，虽然n <= 50时也能跑完，但并非最优。仓库源码采用「一次性预处理、后续直接查表」的策略（见 1641. Count Sorted Vowel Strings.go）：

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 }

makeTable遍历n = 0到n = 50共 51 个取值，逐一用 DFS 求出答案并存入数组。生成的表恰好覆盖题目的全部约束范围1 <= n <= 50（下标 0 的 1 代表空串）。最终主函数退化为一次下标访问（见 1641. Count Sorted Vowel Strings.go）：

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] }

验证表中几个关键值：res[1] = 5、res[2] = 15、res[33] = 66045，与题目三个示例的输出完全吻合。

复杂度分析（打表法）

• 查询阶段：单次查表仅需一次数组下标访问，时间复杂度 O(1)，空间复杂度 O(1)（表大小固定为 51 个整数）；
• 预处理阶段：makeTable需要枚举全部非降序元音串，其数量级为 C(n+4,4)，约 O(n^4)，但由于只在程序启动时执行一次且n <= 50，对整体性能几乎无影响。

打表法的价值在于：它把「正确性容易验证的暴力逻辑」与「运行期的 O(1) 查询」分离开来，非常适合数据范围小、查询次数多的场景。

解题思路二：组合数学 —— 答案就是 C(n+4,4)

原文档给出了更优雅的数学视角，也是本题真正的考点。我们可以把问题做三次等价的重新建模。

建模一：把「非降序串」映射为「5 堆分配」

长度为n的非降序元音串，其字符构成完全由每个元音出现的次数决定。例如n = 2时的ae意味着a出现 1 次、e出现 1 次、其余元音 0 次；oo意味着o出现 2 次。

反过来，只要确定了a、e、i、o、u各自出现多少次（合计必须为n），那么按照元音顺序把这些字符拼接起来，得到的字符串就唯一确定且天然有序。因此问题转化为：

把n个完全相同的小球放入 5 个有编号的盒子（允许空盒），一共有多少种放法？

这正是在数学中被称为**重复组合 / 多重组合（combinations with repetition）**的计数问题：从 5 种元素中允许重复地选取n个，方案数为 C(n+5-1, 5-1) = C(n+4, 4)。

建模二：隔板法（Stars and Bars）直观验证

为什么是 C(n+4,4)？用经典的隔板法可以直观说明。把n个小球排成一列，用 4 块隔板把它们分成 5 段，第k段的长度就是第k个元音出现的次数；相邻两块隔板之间没有球，就表示该元音出现 0 次（允许空盒）。于是问题变成：

在n + 4个位置中，选出 4 个位置放置隔板，其余n个位置放球。

显然方案数为 C(n+4, 4)。这与原文档中「有 n+4 个字母，取 4 次，+4 代表 4 个空操作」的表述是同一回事：多出的 4 个「空操作」就是 4 块隔板。

建模三：直接套用组合公式

根据组合数的定义直接展开：

C(n+4, 4) = (n+4)! / (4! · n!) = (n+1)(n+2)(n+3)(n+4) / 24

仓库源码正是这样实现的（见 1641. Count Sorted Vowel Strings.go）：

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

用示例验算公式

• n = 1：(2 × 3 × 4 × 5) / 24 = 120 / 24 =5；
• n = 2：(3 × 4 × 5 × 6) / 24 = 360 / 24 =15；
• n = 33：(34 × 35 × 36 × 37) / 24 = 1585080 / 24 =66045。

三组结果与题目示例全部一致。由于n <= 50，四个因子的乘积远小于int上限，完全不需要担心溢出问题。

复杂度分析（组合法）

单次计算只需 3 次乘法与 1 次除法，时间复杂度 O(1)，空间复杂度 O(1)，且不需要任何预计算表，是三种方案中最简洁的。

两种解法的对比与选择

从源码结构看，两种解法在仓库中是并列保留的：countVowelStrings打表法侧重展示「暴力正确性」，countVowelStrings1组合法侧重展示「数学优化」。实际生产或刷题场景下，推荐优先使用组合公式；而在需要向他人解释题目语义、或作为教学演示时，DFS 枚举更具可读性。

延伸视角：递推与动态规划

除了文档中的两种解法，还可以从组合恒等式出发得到一个递推视角：设dp[i][j]表示长度为i、以第j个元音（按a,e,i,o,u顺序）结尾的非降序串数量，则有dp[i][j] = dp[i-1][j] + dp[i][j-1]之类的转移关系。可以推断该递推的累加结果最终与 C(n+4,4) 严格等价，因为两者计数的是同一集合。需要说明的是，当前仓库并未提供该 DP 实现，此处仅作为理解公式来源的补充推导，具体实现仍以文档与源码中的打表法、组合法为准。

仓库源码与测试验证

源码与测试文件位置

• 题解实现：leetcode/1641.Count-Sorted-Vowel-Strings/1641. Count Sorted Vowel Strings.go
• 单元测试：leetcode/1641.Count-Sorted-Vowel-Strings/1641. Count Sorted Vowel Strings_test.go
• 原文档：leetcode/1641.Count-Sorted-Vowel-Strings/README.md

测试用例解读

测试文件沿用了 LeetCode-Go 仓库统一的「question / para / ans」结构：para1641封装输入参数n，ans1641封装期望输出，Test_Problem1641内置了题目给出的三组用例（见 1641. Count Sorted Vowel Strings_test.go）：

测试中不仅断言了打表版countVowelStrings的输出，还调用了countVowelStrings1与makeTable，相当于同时验证了组合公式的数值结果，以及打表过程本身不会出错。

如何运行测试

在仓库根目录下，可以针对该题目单独运行测试：

go test -v "./leetcode/1641.Count-Sorted-Vowel-Strings/"

也可以像仓库自带的 gotest.sh 那样对全部题解执行带覆盖率收集的测试：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

本项目以高测试覆盖率作为工程规范（项目描述中即标注 100% test coverage），每道题的_test.go文件与题解实现一一对应，方便读者对照验证。

小结

本题虽是一道简单题，却同时考察了「回溯枚举」「打表优化」与「组合数学建模」三层能力：

1. DFS 回溯 + 打表：用vowels = vowels[index:]保证枚举结果天然非降序，预处理出 51 项常量表后查询为 O(1)；
2. 组合数学 C(n+4,4)：把「非降序元音串」重建成「n 个小球分入 5 个允许为空的盒子」，借助隔板法一步得出闭式解 (n+1)(n+2)(n+3)(n+4)/24；
3. 测试闭环：仓库通过_test.go对两种解法同时断言，并覆盖题目给出的全部示例。

掌握「重复组合」这一建模手法后，诸如「把 n 个相同物品分给 k 个组」一类的问题都可以直接套用 C(n+k-1, k-1)，达到举一反三的效果。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go