LeetCode 题解工作台
将字符串分割为最少的美丽子字符串
给你一个二进制字符串 s ，你需要将字符串分割成一个或者多个 子字符串 ，使每个子字符串都是 美丽 的。 如果一个字符串满足以下条件，我们称它是 美丽 的： 它不包含前导 0 。 它是 5 的幂的 二进制 表示。 请你返回分割后的子字符串的 最少 数目。如果无法将字符串 s 分割成美丽子字符串，请你…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
题目中需要判断一个字符串是否是 的幂的二进制表示，因此，我们不妨先预处理出所有 的幂的数字，记录在哈希表 中。 接下来，我们设计一个函数 ，表示从字符串 的第 个字符开始，到字符串末尾的最少分割次数。那么答案就是 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个二进制字符串 s ，你需要将字符串分割成一个或者多个 子字符串 ，使每个子字符串都是 美丽 的。
如果一个字符串满足以下条件，我们称它是 美丽 的：
- 它不包含前导 0 。
- 它是
5的幂的 二进制 表示。
请你返回分割后的子字符串的 最少 数目。如果无法将字符串 s 分割成美丽子字符串，请你返回 -1 。
子字符串是一个字符串中一段连续的字符序列。
示例 1：
输入：s = "1011" 输出：2 解释：我们可以将输入字符串分成 ["101", "1"] 。 - 字符串 "101" 不包含前导 0 ，且它是整数 51 = 5 的二进制表示。 - 字符串 "1" 不包含前导 0 ，且它是整数 50 = 1 的二进制表示。 最少可以将 s 分成 2 个美丽子字符串。
示例 2：
输入：s = "111" 输出：3 解释：我们可以将输入字符串分成 ["1", "1", "1"] 。 - 字符串 "1" 不包含前导 0 ，且它是整数 50 = 1 的二进制表示。 最少可以将 s 分成 3 个美丽子字符串。
示例 3：
输入：s = "0" 输出：-1 解释：无法将给定字符串分成任何美丽子字符串。
提示：
1 <= s.length <= 15s[i]要么是'0'要么是'1'。
解题思路
方法一：记忆化搜索
题目中需要判断一个字符串是否是 的幂的二进制表示，因此，我们不妨先预处理出所有 的幂的数字，记录在哈希表 中。
接下来，我们设计一个函数 ，表示从字符串 的第 个字符开始，到字符串末尾的最少分割次数。那么答案就是 。
函数 的计算方法如下：
- 如果 ，表示已经处理完了所有字符，那么答案就是 ；
- 如果 ，表示当前字符串包含前导 ，不符合美丽字符串的定义，因此答案是无穷大；
- 否则，我们从 开始枚举子字符串的结束位置 ，用 表示子字符串 的十进制值，如果 在哈希表 中，那么我们就可以将 作为一个美丽子字符串，此时答案就是 。我们需要枚举所有可能的 ，并取所有答案中的最小值。
为了避免重复计算，我们可以使用记忆化搜索的方法。
在主函数中，我们首先预处理出所有 的幂的数字，然后调用 ，如果返回值为无穷大，那么说明无法将字符串 分割成美丽子字符串，答案返回 ，否则返回 的值。
时间复杂度 ，空间复杂度 。其中 是字符串 的长度。
class Solution:
def minimumBeautifulSubstrings(self, s: str) -> int:
@cache
def dfs(i: int) -> int:
if i >= n:
return 0
if s[i] == "0":
return inf
x = 0
ans = inf
for j in range(i, n):
x = x << 1 | int(s[j])
if x in ss:
ans = min(ans, 1 + dfs(j + 1))
return ans
n = len(s)
x = 1
ss = {x}
for i in range(n):
x *= 5
ss.add(x)
ans = dfs(0)
return -1 if ans == inf else ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n^2 * log(maxValue)) due to iterating all substrings and checking power-of-5 condition, where n is string length. Space complexity is O(n) for the DP array. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Recognize that simple greedy splitting often fails due to overlapping substrings and multiple partition paths.
- question_mark
Check for leading zeros carefully as they invalidate the beautiful substring condition.
- question_mark
Expect candidates to explain how DP state transitions prevent redundant recalculation of overlapping prefixes.
常见陷阱
外企场景- error
Assuming all substrings starting with 1 are valid powers of 5 without proper division check.
- error
Ignoring substrings with leading zeros which breaks the beautiful substring rule.
- error
Not considering all possible partition endpoints leading to suboptimal counts.
进阶变体
外企场景- arrow_right_alt
Partition into minimum substrings that are powers of 3 instead of 5.
- arrow_right_alt
Count all possible partitions rather than only minimum ones.
- arrow_right_alt
Restrict substrings to a maximum length and still check for power-of-5.