企业官网建设流程全解析

• 科学计算

本文围绕 LeetCode 双周赛第 108 场第 3 题「将字符串拆分为最少漂亮子字符串」（Partition String Into Minimum Beautiful Substrings）展开，以本仓库 leetcode/biweekly/108/c/README.md 中的官方题解为骨架，结合仓库内配套的 Go 实现、测试样例与测试框架源码，系统讲解从记忆化搜索到递推的完整推导过程，以及该解法在 Python 与 Go 双语言下的落地方式。读完本文，你将掌握：如何用"十进制幂的二进制表示"这一关键观察完成状态压缩、如何借助倒序递推天然规避前导零约束，以及如何利用本仓库的 LeetCode 测试基础设施验证任意实现。

题目背景与核心约束

本题来自力扣双周赛第 108 场（题目编号biweekly-contest-108，对应题目partition-string-into-minimum-beautiful-substrings）。任务如下：

• 输入一个二进制字符串s（仅含0和1，且不包含前导零）。
• 需要将s划分成若干段（子串），每一段都必须是一个"漂亮子串"。
• "漂亮子串"定义为：其十进制表示是 5 的幂（即数值形如 $5^k, k \ge 0$）。
• 求最小划分段数；若无法划分，返回-1。

例如字符串"1011"的十进制值为 11，而 5 的幂依次为 1、5、25、125…。二进制下"101"对应十进制 5，"1"对应 1，因此"1011" = "101" + "1"可以划分成 2 段漂亮子串，答案为 2。

理解这道题的关键在于两个观察：

1. 值域上界：由于s长度为 $n$，其十进制数值严格小于 $2^n$。因此只需要考虑小于 $2^n$ 的 5 的幂。
2. 漂亮子串集合极小：在 $2^{15} = 32768$ 以内，5 的幂只有 $1, 5, 25, 125, 625, 3125, 15625$ 共7 个。也就是说，s中可能出现的"漂亮子串"的二进制形式总共只有 7 种候选。

正是由于候选集合如此之小，预处理全部候选串后，问题就退化为一个非常朴素的字符串划分 DP。

预处理：5 的幂的二进制表示

原文档给出的预处理逻辑是：枚举 $5^i$（从 $i=0$ 开始），只要值小于 $2^{15}$，就把它的二进制字符串形式存入全局变量pow5。仓库配套 Go 实现位于 leetcode/biweekly/108/c/c.go，完整代码如下：

package main import "strconv" var pow5 []string func init() { // 预处理 2**15 以内的 5 的幂 for p5 := 1; p5 < 1<<15; p5 *= 5 { pow5 = append(pow5, strconv.FormatUint(uint64(p5), 2)) } }

这段代码有两点值得说明：

• 循环条件p5 < 1<<15与 README 中"预处理 $2^{15}$ 以内的 5 的幂"完全一致：1<<15是 Go 的移位运算，即 $2^{15}=32768$。循环从p5 = 1（即 $5^0$）开始，每次p5 *= 5，直到下一个幂不小于 $2^{15}$ 为止，共得到 7 个值。
• 进制转换strconv.FormatUint(uint64(p5), 2)是标准库的进制格式化函数，第二个参数2表示按二进制输出。因此pow5中存放的是形如"1"、"101"、"11001"、"1111101"、"1001110001"、"110000110101"、"11110100001001"的字符串。

从仓库源码结构看，之所以把pow5设计成包级全局变量并在init()中填充，是因为测试框架（leetcode/testutil/leetcode.go 中的RunLeetCodeFuncWithFile、RunFuncWithRandomInput）会反复调用minimumBeautifulSubstrings执行多组用例，预处理只做一次即可被所有用例共享，避免重复计算。

为什么是 $2^{15}$？

题目没有直接给出 $2^{15}$ 这个数字，它来自对数据规模的推断：README 中明确说明"由于测试数据很多，可以用全局变量，预处理 $2^{15}$ 以内的 5 的幂"。可以推断，该题数据范围中 $n \le 15$（即输入二进制串长度至多 15），因此任何漂亮子串的数值都不可能达到 $2^n$，枚举小于 $2^{15}$ 的 5 的幂即覆盖了全部候选。如果你的输入规模更大，这一上限需要相应放大，但候选数量增长极为缓慢（10 的幂增长，对应到二进制串个数也极少），不影响整体思路。

记忆化搜索：自顶向下的最小划分

状态设计

定义 $\textit{dfs}(i)$ 表示：将后缀s[i:]（从s[i]开始到末尾的子串）划分成若干漂亮子串的最小段数。那么：

• 递归边界：$\textit{dfs}(n) = 0$，空后缀不需要划分。
• 递归入口：$\textit{dfs}(0)$，即整个字符串的最小划分段数。
• 不可行情况：若s[i] == '0'（该段以 0 开头，会形成前导零，而 5 的幂的二进制表示不可能有前导零，也不允许前导零的子串），或者s[i:]无法匹配任何候选串，则 $\textit{dfs}(i) = \infty$（Python 中用inf，Go 中用n+1这类上界值）。

状态转移

枚举pow5中的每个候选串t（长度为 $m$），若s[i:i+m] == t，则可以把这一段切下来，剩下部分递归求解，因此有：

$$ \textit{dfs}(i) = \textit{dfs}(i+m) + 1 $$

对所有可行候选取最小值即可。

Python 实现（原文档代码）

# 预处理 2**15 以内的 5 的幂 pow5 = [bin(5 ** i)[2:] for i in range(7)] class Solution: def minimumBeautifulSubstrings(self, s: str) -> int: n = len(s) @cache def dfs(i: int) -> int: if i == n: return 0 if s[i] == '0': return inf # 不能包含前导 0 res = inf for t in pow5: if i + len(t) > n: break if s[i: i + len(t)] == t: # 忽略切片的时间，这里的比较视作均摊 O(1) res = min(res, dfs(i + len(t)) + 1) return res ans = dfs(0) return ans if ans < inf else -1

实现细节：

• pow5 = [bin(5 ** i)[2:] for i in range(7)]与 Go 版init()等价：bin(x)[2:]去掉0b前缀即得二进制字符串，range(7)恰好覆盖 $i=0..6$，对应 7 个小于 $2^{15}$ 的 5 的幂。
• 内层循环在i + len(t) > n时break，是因为pow5中的字符串按长度递增排列，一旦当前候选超出后缀长度，后续更长的候选必然也超出，可以提前终止。
• @cache（Python 3.9+ 的functools.cache）负责记忆化，保证每个dfs(i)只被计算一次。
• 返回时判断ans < inf：inf与任意整数比较时，整数值一定更小，因此该条件等价于"存在可行划分"。

递推版：倒序遍历规避前导零

README 中强调："按照视频中的做法，1:1 翻译成递推。倒着遍历的好处是方便判断是否有前导零。"

为什么倒序？

记忆化搜索天然从位置 0 向尾部推进，而递推若正序（从左到右）填表，会面临一个问题：划分的第一段以s[0]开头，而题目保证输入本身没有前导零，正序填表时状态f[i]表示s[0:i]的划分，处理起来并不直观，且"当前段能否以 0 开头"的判断分散在转移中。倒序填表则让f[i]直接对应后缀s[i:]，与 $\textit{dfs}(i)$ 一一对应：从i = n-1一路算到i = 0，每一轮只需检查s[i]是否为零，零则直接跳过（不可行），否则枚举候选串尝试匹配。这与原题解的递归语义完全同构，翻译成本最低。

Python 递推实现（原文档代码）

# 预处理 2**15 以内的 5 的幂 pow5 = [bin(5 ** i)[2:] for i in range(7)] class Solution: def minimumBeautifulSubstrings(self, s: str) -> int: n = len(s) f = [inf] * n + [0] for i in range(n - 1, -1, -1): if s[i] == '0': continue # 不能包含前导 0 for t in pow5: if i + len(t) > n: break if s[i: i + len(t)] == t: # 忽略切片的时间，这里的比较视作均摊 O(1) f[i] = min(f[i], f[i + len(t)] + 1) return f[0] if f[0] < inf else -1

注意f = [inf] * n + [0]的写法：[inf] * n得到长度 $n$ 的列表，再拼接[0]，恰好构造出长度为 $n+1$ 的数组，其中f[n] = 0正是递归边界 $\textit{dfs}(n)=0$ 的递推对应物。

Go 递推实现（仓库源码）

仓库中的 leetcode/biweekly/108/c/c.go 给出了与 README 完全一致的 Go 实现：

func minimumBeautifulSubstrings(s string) int { n := len(s) f := make([]int, n+1) for i := n - 1; i >= 0; i-- { f[i] = n + 1 if s[i] == '0' { continue } for _, t := range pow5 { if i+len(t) > n { break } if s[i:i+len(t)] == t { f[i] = min(f[i], f[i+len(t)]+1) } } } if f[0] > n { return -1 } return f[0] } func min(a, b int) int { if b < a { return b }; return a }

Go 版与 Python 版有三处语言差异需要留意：

1. "无穷大"的表示：Python 用inf，Go 用n + 1作为不可行标记。由于最多划分 $n$ 段（每段一个字符），n+1必然大于任何合法答案，因此f[0] > n与 Python 的f[0] < inf判断等价。
2. 字符串切片比较：s[i:i+len(t)] == t是 Go 的字节串比较，i+len(t)保证不越界（内层循环在i+len(t) > n时已break）。
3. min函数：该仓库使用go 1.23（见 go.mod），min已是内置函数，这里手写min(a, b)是为了兼容旧版本 Go 编译环境的写法。

复杂度分析

README 中给出的复杂度结论如下：

• 时间复杂度：$\mathcal{O}(n^2)$，其中 $n$ 为s的长度。动态规划的时间复杂度 = 状态个数 × 单个状态的计算时间。本题状态个数为 $\mathcal{O}(n)$（每个位置一个状态），单个状态需要枚举 7 个候选串并逐一比较，枚举过程本身是 $\mathcal{O}(7) = \mathcal{O}(1)$ 级别的常数开销；字符串比较中，由于pow5内各候选串的公共前缀很短，绝大多数比较在很短的位数内就失配，可视为均摊 $\mathcal{O}(1)$，因此单个状态计算时间为 $\mathcal{O}(n)$（最坏情况是某次匹配成功需要比较完整长度），总时间复杂度为 $\mathcal{O}(n^2)$。
• 空间复杂度：$\mathcal{O}(n)$，仅需一个长度为 $n+1$ 的 DP 数组；pow5是固定大小的预处理数据，不随 $n$ 增长。

值得补充的是：若不使用"失配即退出"的均摊论证，把每次字符串比较都算作 $\mathcal{O}(n)$，则复杂度会上升为 $\mathcal{O}(n^2 \cdot \sum|t|)$，但 7 个候选串的最大长度为 14，常数很小，实际运行仍然非常快。

仓库中的测试与验证体系

测试用例文件

仓库为本题提供了手写测试数据文件 leetcode/biweekly/108/c/c.txt，内容是"输入字符串 + 期望输出"成对排列，共 3 组：

"1011" 2 "111" 3 "0" -1

这 3 组数据正好覆盖了三种典型情形：

• "1011"→ 2：可行划分"101" + "1"（对应 $5 + 1$），答案为 2；
• "111"→ 3：二进制 111 即十进制 7，不是 5 的幂，且 7 以内的 5 的幂只有 1 和 5，"111"无法匹配任何候选（"11"、"111"都不是 5 的幂的二进制），只能拆成 3 个"1"，答案为 3；
• "0"→ -1：以 0 开头无法形成漂亮子串，返回-1。

测试驱动代码

leetcode/biweekly/108/c/c_test.go 通过仓库封装的测试框架驱动：

func Test_c(t *testing.T) { targetCaseNum := 0 // -1 if err := testutil.RunLeetCodeFuncWithFile(t, minimumBeautifulSubstrings, "c.txt", targetCaseNum); err != nil { t.Fatal(err) } if err := testutil.RunFuncWithRandomInput(t, minimumBeautifulSubstrings); err != nil { t.Fatal(err) } }

其中RunLeetCodeFuncWithFile的实现位于 leetcode/testutil/leetcode.go（L340-L370）：它读取c.txt，按"每 2 行一组"解析成 (输入, 期望输出) 用例，再用反射调用被测试函数逐一比对。targetCaseNum = 0表示运行全部用例；若设为正数则只运行指定用例，设为-1则运行最后一组，且单用例通过后会自动继续跑完全部用例（对应源码L320-L323的递归逻辑）。

第二行的RunFuncWithRandomInput是随机对拍：随机生成输入并调用函数，用于在函数具备"输入 → 输出"单调可验证性质时做补充回归（对本题而言主要起到跑通、防 panic 的作用）。

题目来源

c_test.go末尾注释标明了本题的两条链接（双周赛 108 场第三题及题目独立页），均为 LeetCode 官方地址，本文不再重复给出外部链接。

核心思路复盘

最后把整道题的解题链条浓缩为四步，便于在同类"字符串划分 + 数值性质"问题中复用：

1. 压缩候选集：利用数值上界（二进制串长度 $n$ ⇒ 数值 < $2^n$）大幅缩小"合法段"的枚举范围，本题中 5 的幂只有 7 个二进制候选串。
2. 定义后缀状态：$\textit{dfs}(i)$ = 后缀s[i:]的最小划分段数，边界 $\textit{dfs}(n)=0$，不可行记为无穷大。
3. 枚举转移：逐个匹配候选串t，匹配成功则 $\textit{dfs}(i) = \min(\textit{dfs}(i+m)+1)$。
4. 倒序翻译成递推：f[n] = 0，从i = n-1倒推到i = 0，天然处理前导零约束，最终f[0] > n时返回-1。

这套"记忆化搜索 → 1:1 翻译递推"的方法，正是该仓库题解 README（leetcode/biweekly/108/c/README.md）强调的通用训练路径；配合仓库自带的 Go 实现与测试框架，可以随时go test验证任意一步改写（例如把pow5上限改为 $2^{20}$、把匹配方式换成字符串哈希）的正确性。

• 科学计算