LeetCode 题解工作台
长度为 n 的开心字符串中字典序第 k 小的字符串
一个 「开心字符串」定义为： 仅包含小写字母 ['a', 'b', 'c'] . 对所有在 1 到 s.length - 1 之间的 i ，满足 s[i] != s[i + 1] （字符串的下标从 1 开始）。 比方说，字符串 "abc" ， "ac"，"b" 和 "abcbabcbcb" 都是开心…
2
题型
8
代码语言
3
相关题
当前训练重点
中等 · 回溯·pruning
答案摘要
我们用一个字符串 来记录当前的字符串，初始时为空字符串。然后，我们设计一个函数 ，用来生成所有长度为 的开心字符串。 函数 的具体实现如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 回溯·pruning 题型思路
题目描述
一个 「开心字符串」定义为：
- 仅包含小写字母
['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
我们用一个字符串 来记录当前的字符串，初始时为空字符串。然后，我们设计一个函数 ，用来生成所有长度为 的开心字符串。
函数 的具体实现如下：
- 如果当前字符串的长度等于 ，则将当前字符串加入答案数组 中，然后返回；
- 如果答案数组的长度大于等于 ，则直接返回；
- 否则，我们遍历字符集 ，对于每个字符 ，如果当前字符串为空，或者当前字符串的最后一个字符不等于 ，则将字符 加入当前字符串，然后递归调用 ，递归结束后，将当前字符串的最后一个字符删除。
最后，我们判断答案数组的长度是否小于 ，如果是，则返回空字符串，否则返回答案数组的第 个元素。
时间复杂度 ，空间复杂度 。其中 为字符串长度。
class Solution:
def getHappyString(self, n: int, k: int) -> str:
def dfs():
if len(s) == n:
ans.append("".join(s))
return
if len(ans) >= k:
return
for c in "abc":
if not s or s[-1] != c:
s.append(c)
dfs()
s.pop()
ans = []
s = []
dfs()
return "" if len(ans) < k else ans[k - 1]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) due to the backtracking search generating each string step by step. Space complexity is O(1) since the algorithm does not store the entire list of happy strings, only the current string being constructed. |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Candidate demonstrates the ability to think recursively and apply pruning effectively.
- question_mark
Candidate's understanding of backtracking search is sound, especially regarding early termination of invalid branches.
- question_mark
Candidate efficiently manages time and space complexity considerations when implementing the solution.
常见陷阱
外企场景- error
Failing to prune branches during the backtracking search, leading to excessive computation.
- error
Incorrectly handling the case where k exceeds the total number of valid strings.
- error
Not ensuring adjacent characters are different during string construction, leading to invalid happy strings.
进阶变体
外企场景- arrow_right_alt
Extend the problem to handle strings with larger lengths, testing the scalability of the solution.
- arrow_right_alt
Allow for custom sets of characters to be used for generating happy strings.
- arrow_right_alt
Implement the solution iteratively rather than recursively to explore different approaches.