)
【LetMeFly】1415.长度为 n 的开心字符串中字典序第 k 小的字符串：DFS构造 / 数学O(n)
力扣题目链接：https://leetcode.cn/problems/the-k-th-lexicographical-string-of-all-happy-strings-of-length-n/
一个 「开心字符串」定义为：
- 仅包含小写字母
['a', 'b', 'c']. - 对所有在
1到s.length - 1之间的i，满足s[i] != s[i + 1]（字符串的下标从 1 开始）。
比方说，字符串"abc"，"ac"，"b"和"abcbabcbcb"都是开心字符串，但是"aa"，"baa"和"ababbc"都不是开心字符串。
给你两个整数n和k，你需要将长度为n的所有开心字符串按字典序排序。
请你返回排序后的第 k 个开心字符串，如果长度为n的开心字符串少于k个，那么请你返回空字符串。
示例 1：
输入：n = 1, k = 3输出："c"解释：列表 ["a", "b", "c"] 包含了所有长度为 1 的开心字符串。按照字典序排序后第三个字符串为 "c" 。
示例 2：
输入：n = 1, k = 4输出：""解释：长度为 1 的开心字符串只有 3 个。
示例 3：
输入：n = 3, k = 9输出："cab"解释：长度为 3 的开心字符串总共有 12 个 ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"] 。第 9 个字符串为 "cab"
示例 4：
输入：n = 2, k = 7输出：""
示例 5：
输入：n = 10, k = 100输出："abacbabacb"
提示：
1 <= n <= 101 <= k <= 100
解题方法一：DFS构造
写一个dfs函数接收已经构造的字符串并继续构造字符串：
- 如果之前字符串已经长度为
n了，就看看这是不是第k次长度为n。如果是，则说明找到了答案；否则，不继续向后追加字符串，结束这层递归在其他层递归继续寻找答案。 - 否则，尝试把
abc中每个和上一个字符(如有)不同的字符拼接到字符串上并递归。
特别的，我们可以控制这个函数的返回值，返回true代表已经找到了最终答案，可以不再进行后续递归。
- 时间复杂度O ( n k ) O(nk)O(nk)
- 空间复杂度O ( n ) O(n)O(n)
AC代码
C++
/* * @LastEditTime: 2026-03-14 23:29:38 */classSolution{private:intn,k;string ans;charcan[3]={'a','b','c'};// dfs and return if can stopbooldfs(string now){if(now.size()==n){k--;if(!k){ans=now;returntrue;}returnfalse;}charlast=now.empty()?'0':now.back();for(inti=0;i<3;i++){if(can[i]==last){continue;}if(dfs(now+can[i])){returntrue;}}returnfalse;}public:stringgetHappyString(intn,intk){this->n=n,this->k=k;dfs("");returnans;}};#ifdefined(_WIN32)||defined(__APPLE__)/* 1 3 c */intmain(){inta,b;while(cin>>a>>b){Solution sol;cout<<sol.getHappyString(a,b)<<endl;}return0;}#endif解题方法二：数学直接找
长度为n nn的字符串一共有多少种开心字符串呢？
第一个字符有3 33种选择，后续每个字符有2 22种选择，共计3 × 2 n − 1 3\times2^{n-1}3×2n−1种。
如果k > 3 × 2 n − 1 k\gt 3\times2^{n-1}k>3×2n−1则答案不存在，返回空串。
第k kk个开心字符串的每一位分别应该对应哪个字符呢？很简单，我们只需要计算下这个字符后面字符串有多少种。
举个例子：
- 假设后面字符串有2 2 2^222共4种，而当前k = 3 ≤ 4 k=3\leq 4k=3≤4，那么当前字符选哪个？当然选能选的字符中第一个就够了；
- 假设后面字符串有2 2 2^222共4种，而当前k = 5 < 4 k=5\lt 4k=5<4，那么当前字符选哪个？当然选能选的字符中第二个，因为选第一个的话后面最多4 44种情况，到不了k = 5 k=5k=5。
PS: 上面的“能选的字符”指的是属于
abc且和前一个字符不同的字符。
选完这个字符后，令k kk对剩余种类数取模，并更新剩余字符的种类数。
为什么取模呢？
- 仍然假设后面字符串有2 2 2^222共4种，而当前k = 5 < 4 k=5\lt 4k=5<4，假设当前可选字符为
ab，那么相当于当前选a时候后面共有4 44个开心字符串，后面选完了当前字符确定选b了，后面还需要5 % 4 = 1 5\%4=15%4=1个开心字符串，使得总开心字符串数是当前k = 5 k=5k=5个。
我们也可以将k − 1 k-1k−1以便后面的取模整除运算。
- 时间复杂度O ( n ) O(n)O(n)
- 空间复杂度O ( n ) O(n)O(n)
AC代码
C++
/* * @LastEditTime: 2026-03-14 23:21:37 */classSolution{public:stringgetHappyString(intn,intk){intremain=1<<(n-1);if(k>3*remain){return"";}k--;chartoChoose[3]={'a','b','c'};string ans;ans.push_back(toChoose[k/remain]);for(inti=1;i<n;i++){k%=remain;remain>>=1;intth=k/remain;if(toChoose[th]>=ans.back()){th++;}ans.push_back(toChoose[th]);}returnans;}};感觉描述得还不错。
同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
千篇源码题解已开源
