将字符串分割为最少的美丽子字符串

难度: Medium

给你一个二进制字符串 s ，你需要将字符串分割成一个或者多个 子字符串 ，使每个子字符串都是美丽的。

如果一个字符串满足以下条件，我们称它是美丽的：

它不包含前导 0 。
它是 5 的幂的 二进制 表示。

请你返回分割后的子字符串的最少数目。如果无法将字符串 s 分割成美丽子字符串，请你返回 -1 。

子字符串是一个字符串中一段连续的字符序列。

示例 1：

输入：s = "1011"
输出：2
解释：我们可以将输入字符串分成 ["101", "1"] 。
- 字符串 "101" 不包含前导 0 ，且它是整数 5¹ = 5 的二进制表示。
- 字符串 "1" 不包含前导 0 ，且它是整数 5⁰ = 1 的二进制表示。
最少可以将 s 分成 2 个美丽子字符串。

示例 2：

输入：s = "111"
输出：3
解释：我们可以将输入字符串分成 ["1", "1", "1"] 。
- 字符串 "1" 不包含前导 0 ，且它是整数 5⁰ = 1 的二进制表示。
最少可以将 s 分成 3 个美丽子字符串。

示例 3：

输入：s = "0"
输出：-1
解释：无法将给定字符串分成任何美丽子字符串。

提示：

1 <= s.length <= 15
s[i] 要么是 '0' 要么是 '1' 。

Submission

运行时间: 32 ms

内存: 16.2 MB

class Solution:
    def minimumBeautifulSubstrings(self, s: str) -> int:
        r=[bin(5**x)[2:] for x in range(7)]
        
        @cache
        def dfs(s):
            if len(s)==0:
                return 0
            mi=float("inf")
            if s[0]=="0":
                return mi
            for x in r:
                if len(x)<=len(s):
                    if s[:len(x)]==x:
                        mi=min(mi,dfs(s[len(x):])+1)
            return mi
        
        r=dfs(s) 
        return r if r!=float("inf") else -1

Explain

此题解采用深度优先搜索（DFS）与记忆化搜索的方法来解决问题。首先，计算出所有可能的美丽子字符串，即5的幂次的二进制表示，由于s的最大长度为15，计算到5^6即可覆盖所有情况。然后，使用递归函数`dfs`来尝试所有可能的子字符串分割方式，每次尝试匹配已知的美丽子字符串，并递归地处理剩余的字符串部分。如果当前字符串的首字符是'0'，则直接返回无穷大（表示不可能分割成美丽子字符串）。如果能匹配到一个美丽子字符串，就在此基础上继续处理，寻找最小的分割次数。最后，如果得到的结果是无穷大，则说明无法将字符串分割成美丽子字符串，返回-1，否则返回分割的最小次数。

时间复杂度: O(7^n)

空间复杂度: O(n)

class Solution:
    def minimumBeautifulSubstrings(self, s: str) -> int:
        # 计算5的幂次的二进制表示，并存储
        r=[bin(5**x)[2:] for x in range(7)]
        
        @cache
        def dfs(s):
            if len(s)==0:
                return 0
            mi=float(\"inf\")
            if s[0]==\"0\":
                return mi
            for x in r:
                if len(x)<=len(s):
                    if s[:len(x)]==x:
                        mi=min(mi,dfs(s[len(x):])+1)
            return mi
        
        r=dfs(s) 
        return r if r!=float(\"inf\") else -1

Explore

题解选择使用深度优先搜索（DFS）主要是因为问题的本质是在寻找所有可能的分割方式，并从中选择最优解，这自然适合使用回溯法来探索所有可能的子字符串组合。相比之下，动态规划虽然也可以解决此问题，但是其空间复杂度可能较高，因为需要存储每一个子问题的解。而贪心算法不适用于此问题，因为局部最优选择并不一定能导致全局最优解。DFS加上记忆化可以有效地减少重复计算，提高效率。

是的，美丽子字符串定义为'5的幂次的二进制表示'，由于二进制表示中5的幂次（例如1, 5, 25, 125等）转换为二进制后自然不会有前导0。因此，所有这些美丽子字符串都不包含前导0。

不完全是这样。题解中特别提到首字符为'0'时返回无穷大，是因为任何有效的美丽子字符串不以'0'开头。如果在分割的过程中遇到任何以'0'开头的子字符串段，这种分割方式都是无效的。因此，不仅是首字符，任何分割后子字符串的首字符若为'0'，都会导致该分割方式被视为无效。

在题解中，记忆化是通过装饰器`@cache`来实现的，这通常是Python中functools模块提供的一个功能，用于自动存储函数的输入和对应的输出结果。在这个场景中，`dfs`函数递归处理字符串，每次调用都基于当前的子字符串`s`，因此，记忆化是基于子字符串`s`作为键来存储每个子字符串的最小分割次数。这样可以避免重复计算相同字符串的分割结果，极大提高了效率。