题目描述
思路解析
一句话答案：LeetCode 1625 执行操作后字典序最小的字符串：两种操作能到的串只有有限个，用 BFS 把可达串全枚举一遍、靠 visited 判重取最小，时间 O(n²) 级。
两种操作能到的串里，哪个字典序最小
给一个长度为偶数、只含数字的字符串 s 和两个整数 a、b。你能反复用两种操作：一种给所有奇数下标的数字加上 a、加完对 10 取余；另一种把整串向右轮转 b 位，也就是把末尾 b 个字符搬到最前。操作次数不限、先后随意，问能到达的串里字典序最小的是哪个。字典序即逐位比，第一个不同的位谁小整串就小。
操作能用任意多次，怎么保证枚举得完
操作次数不限、顺序不限，若按『试一条操作序列、再换一条』去枚举，序列有无穷多条、试不完还绕圈。别盯操作序列，改盯它们能生成的串——真正不同的串只有有限个，一个不漏找出来就行。
为什么可达的串只有有限个，BFS 怎么全枚举
轮转转满一圈回原样，顶多 n 种结果；奇数位反复加 a，值在 0 到 9 间循环、最多 10 种；b 为奇数时轮转把奇偶下标错开、偶数位也会被加到，再乘最多 10 倍。乘起来可达串是 O(n) 量级、顶多上百个，有限就枚举得完。
把每个串当节点、两种操作各连一个邻居，从起点 s 跑 BFS，也就是广度优先搜索：拿队列存待处理的串，用集合 visited 记已见过的串。每回从队头取一个串，先用它更新最小答案，再算两个邻居、没进过 visited 的入队。队列空时可达串都比过一遍，答案就是记下的最小值。
题面的「74」，a=5、b=1，队列怎么清空
起点「74」进队列、答案先记「74」。取出「74」：累加只动奇数下标 1 的 4，加 5 得 9 成「79」；右移得「47」，两个新串入队。取出「79」比「74」大、答案不动，它累加时 9 加 5 得 14、取余落回 4 又是「74」撞 visited 跳过，右移得「97」。取出「47」第一位 4 小于 7，答案首次刷成「47」；累加得「42」，右移回「74」已见过。
「97」不更小、累加得「92」；「42」第二位更小、答案刷成「42」，右移得「24」；「92」右移得「29」；「24」第一位 2 小于 4、答案刷成「24」，邻居都见过；末尾「29」也不更小。队列清空，「74」「79」「47」「97」「42」「92」「24」「29」八个可达串全走完，答案停在「24」，正是题面结果。
这套搜索的时间和空间花在哪
设串长 n。可达串是 O(n) 量级、常数最多百来个：轮转顶多 n 种，奇数位累加顶多 10 种，b 为奇数时偶数位再乘最多 10 种。每个串生成、比字典序、进集合各要 O(n)，时间约 O(n²) 级。visited 和队列峰值要装下全部可达串、每个长 n，空间也是 O(n²) 级。
把奇数位数成第几个数字，搜索就建在错邻居上
最伤的是数错位置：下标从 0 数起，奇数下标 1、3、5 才被累加，偶数下标 0、2、4 一直不动。若顺着『第几个数字』从 1 数去加，就把偶数位也改了，往后每个邻居都错。
右移 b 位是把末尾 b 个字符搬到最前，别写反成左移或截错段，Python 里就是 s[-b:] + s[:-b]。判重也省不得：操作能无限次用，不记 visited 队列就绕环、清不空；比大小按等长字符串逐位比，别转成整数，「0011」一转成 11、前导零丢了字典序就比错。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这套:把串当节点、两种操作当出边,BFS 逐个出队;每出队一个就更新最小答案,再把它的两个邻居里没访问过的入队,visited 判重。下面每一帧都在套它。
先看画面怎么摆。上面这排是当前要处理的串,这会儿是初始串 「74」。下标 0 是偶数位 7,累加操作永远不碰它;下标 1 是奇数位 4,累加会落在它头上。右边「已访问 visited」是判重集合,现在只装着起点 「74」。队列里也只有 「74」 一个,当前最优答案先记成 「74」。
从队头取出 「74」 来处理。先拿它和当前最优比一比,它就是最优本身,不更小,最优保持 「74」 不变。接着要对它做两种操作,生成两个邻居。
第一种操作:累加。只动奇数下标 1 上的数字,4 加 5 等于 9,没超过 9 不用绕回,偶数位 7 原样不动,得到 「79」。visited 里没有 「79」,是个新串,标成已访问并塞进队尾。
第二种操作:右移 1 位,把末尾 1 个字符 4 搬到最前面,「74」 变成 「47」。visited 里也没有 「47」,新串,标记已访问、入队。现在队列里排着 「79」 和 「47」。
出队下一个 「79」。和当前最优 「74」 比,「79」 大于 「74」,字典序更大,最优不更新,仍是 「74」。再对它做两种操作。
对 「79」 累加:奇数位 9 加 5 等于 14,超过 9 了,对 10 取余落回成 4,得到 「74」。可是 「74」 早就在 visited 里了,说明绕回了起点,跳过不再入队。这一步正是判重在拦环。
对 「79」 右移 1 位,末尾的 9 挪到最前,得到 「97」。visited 里没有 「97」,新串,入队。
出队 「47」。和当前最优 「74」 比,第一位 4 就小于 7,「47」 字典序更小,最优更新成 「47」。这是第一次刷新答案。
对 「47」 累加:奇数位 7 加 5 等于 12,取余落回 2,偶数位 4 不动,得到 「42」。新串,入队。
对 「47」 右移 1 位,末尾 7 搬到前面,变回 「74」。又是起点,visited 里有,跳过。
出队 「97」。和当前最优 「47」 比,第一位 9 大于 4,更大,最优不更新,仍是 「47」。
对 「97」 累加:奇数位 7 加 5 等于 12,取余成 2,得到 「92」。新串,入队。
对 「97」 右移 1 位,末尾 7 挪到前面,得到 「79」。visited 里已经有 「79」,跳过。
出队 「42」。和当前最优 「47」 比,前两位都比一比,第一位都是 4,第二位 2 小于 7,所以 「42」 更小,最优更新成 「42」。
对 「42」 累加:奇数位 2 加 5 等于 7,得到 「47」。「47」 之前访问过了,跳过。
对 「42」 右移 1 位,末尾 2 搬到最前,得到 「24」。这是个新串,入队。注意这个 「24」 正是最后的答案,但搜索还没结束,先继续走。
出队 「92」。和当前最优 「42」 比,第一位 9 大于 4,更大,最优不更新。
对 「92」 累加:奇数位 2 加 5 等于 7,得到 「97」。访问过了,跳过。
对 「92」 右移 1 位,末尾 2 挪到前,得到 「29」。新串,入队。到这儿可达串已经凑齐 8 个了。
出队 「24」。和当前最优 「42」 比,第一位 2 小于 4,「24」 更小,最优更新成 「24」。这就是最终答案了,不过队列还没空,得把流程走完才能确定。
对 「24」 做两种操作:累加得到 「29」,右移得到 「42」。这两个串 visited 里都有,全部跳过,不再产生新节点。visited 已经集满 8 个串,搜索快到头了。
出队最后一个 「29」。和当前最优 「24」 比,第一位 2 相同,第二位 9 大于 4,更大,最优不更新。
对 「29」 累加得到 「24」、右移得到 「92」,两个都在 visited 里,全跳过。没有新串入队,队列就此清空。
队列空了,8 个可达串全都处理完,visited 里 「74」「79」「47」「97」「42」「92」「24」「29」 一个不少。整个过程里最优答案从 「74」 一路被刷新到 「47」、「42」、最后停在 「24」。所以从 「74」 出发能得到的字典序最小串就是 「24」,和开头说的对上了。
边界:「0011」 怎么操作都变大,初始串就是最小;「10」 先右移成 「01」 再给奇数位加 9 取余得 「00」;「00」 一加就变大,本身已最小。
三个追问:可达串数有限(O(n) 量级)所以 BFS 必停;换成 DFS 加 visited 答案一样;也能枚举旋转与累加次数直接构造,但 BFS 最直观不易错。
参考代码
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 findLexSmallestString(self, s: str, a: int, b: int) -> str: q = deque([s]) vis = {s} ans = s while q: s = q.popleft() if ans > s: ans = s t1 = ''.join( [str((int(c) + a) % 10) if i & 1 else c for i, c in enumerate(s)] ) t2 = s[-b:] + s[:-b] for t in (t1, t2): if t not in vis: vis.add(t) q.append(t) return ans复杂度
- 时间：O(n²) 级，设串长 n。右移最多产生 n 种不同旋转;给奇数位反复累加 a,不同结果最多 10 种,若 b 为奇数旋转会把奇偶位错开、偶数位也可能被累加,再多至多 10 倍。所以可达串数是 O(n) 量级(常数最多 100)。每个串生成、比较字典序、丢进哈希集合各要 O(n);BFS 每个串扩展 2 个邻居。合起来大约 O(n²) 级(含这个常数 100)
- 空间：O(n²) 级，按峰值算。visited 与队列里最多同时存下全部可达串,可达串数是 O(n) 量级,每个串长 n,所以存它们要 O(n) 乘以 n,即 O(n²) 级。这就是整个过程占用的内存峰值
易错点
面试追问把动画讲成自己的话
追问操作能用任意多次, 为什么 BFS 还能在有限步内停下来?
追问用深度优先搜索行不行?
追问能不能不搜索, 直接构造最优解?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
生成平衡数组的方案数
LeetCode 1664 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题