题目描述
思路解析动画文字版
记牢两句:按 a b c 顺序放、避开和前一位相同的字母,收集顺序天然是字典序;凑够 k 个立刻刹车。下面每一帧都在套它。
先看画面。上面这排 a、b、c 是每一位能用的三个字母,谁和前一位重复就在它上面打叉、本位不能选。中间 path 是正在拼的串,从空开始一位一位往后接。右边结果区按字典序收集已经拼好的开心串。我们从最小的字母开头往下搜,收集到第 9 个就停。
第 1 位起手。前面没有字符,a、b、c 都能放,按字典序先挑最小的 a。path 现在是 a。
到第 2 位。前一位是 a,再放 a 就相邻重复了,给 a 打叉跳过。下一个最小的是 b,和 a 不同,放下,path 成了 ab。
第 3 位,前一位是 b,b 打叉不能用。按字典序最小的 a 和 b 不同,放 a。三位拼满,凑出 aba,这是收集到的第 1 个开心字符串,收进结果区。
退回第 3 位换下一个。a 试过了,b 又和前一位重复,于是落到 c。拼成 abc,第 2 个,收下。
第 2 位是 b 的两支搜完了,退回第 2 位。a 和前一位重复要打叉,b 刚搜过,这次轮到 c,path 变成 ac。
第 3 位前一位是 c,c 打叉。最小的 a 可以放,拼出 aca,第 3 个。
再退回换下一个,a 用过、c 重复,放 b,得到 acb,第 4 个。a 打头的四个开心串到齐了。
a 当第 1 位的分支全部走完,依次收了 aba、abc、aca、acb 四个。把 path 一路退回空,回到第 1 位换下一个字母。
第 1 位这次放 b,重新往后搜。
第 2 位前一位是 b,b 打叉,最小的 a 和它不同,放 a,path 是 ba。
第 3 位前一位是 a,a 跳过,放 b,拼成 bab,第 5 个。
退回换下一个,b 用过,放 c,得到 bac,第 6 个。
退回第 2 位,a 这支搜完、b 和前一位重复,换 c,path 成了 bc。
第 3 位前一位是 c,放最小的 a,拼出 bca,第 7 个。
再换下一个,a 用过、c 重复,放 b,得到 bcb,第 8 个。b 打头的四个也凑齐了。
b 当第 1 位的分支也清完,又收了四个,现在一共 8 个。退回空 path,第 1 位换最后一个字母 c。
第 1 位放 c。我们只差第 9 个了,盯紧这一支。
第 2 位前一位是 c,c 打叉,放最小的 a,path 是 ca。
第 3 位前一位是 a,a 跳过,放 b,拼成 cab。这正好是收集到的第 9 个,也就是要找的答案。一凑够 9 个就立刻刹车,后面的串不用再生成。
回头看结果区,按字典序排好的开心串依次是 aba、abc、aca、acb、bab、bac、bca、bcb、cab,第 9 个正是 cab,把它返回就是答案。跟开头说的对上了。
边界:n 等于 1 时只有 abc 三个;k 超过总数返回空串;第 1 个总是最小的 aba 这类交替串。
三个追问:提前 return 是为剪枝提速;可用计数法 O(n) 直接定位第 k 个;换成 m 种字母总数变 m·(m-1)^(n-1)。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def getHappyString(self, n: int, k: int) -> str: def dfs(): if len(ans) >= k: return if len(s) == n: ans.append("".join(s)) 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]复杂度
- 时间：O(n·k)，n 是串长,k 是要找的名次。每拼出一个完整的开心串花 O(n),最多拼到第 k 个就停,所以是 O(n·k)。最坏当 k 接近长度 n 的开心串总数 3·2^(n-1) 时,会退化成把它们几乎全造一遍,即 O(n · 2^n)
- 空间：O(n·k)，按峰值算,主要花在 ans 里存下已收集的最多 k 个串,每个长 n,合起来 O(n·k);递归深度只有 n,栈是 O(n)。若改成数够 k 个就直接返回、不把串都存下来,辅助空间能压到 O(n)
易错点
面试追问把动画讲成自己的话
追问代码里那句「ans 个数到了 k 就 return」,去掉会怎样?
追问能不能不做深搜,直接用 O(n) 算出第 k 个?
追问如果字母不止 a、b、c,而是 m 种字母,做法和复杂度怎么变?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
拆分字符串使唯一子字符串的数目最大
LeetCode 1593 · 中等 · 沿着 回溯套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题