Medium

题目描述

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

如果一个字符串满足以下条件，则认为它是美丽的：

  • 它不包含前导零。
  • 它是某个 5 的幂的二进制表示。

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

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

示例 1：

输入：s = "1011"
输出：2
解释：我们可以将给定的字符串分割为 ["101", "1"]。
- 字符串 "101" 不包含前导零，是整数 5^1 = 5 的二进制表示。
- 字符串 "1" 不包含前导零，是整数 5^0 = 1 的二进制表示。
可以证明 2 是 s 可以分割成的美丽子字符串的最少数目。

示例 2：

输入：s = "111"
输出：3
解释：我们可以将给定的字符串分割为 ["1", "1", "1"]。
- 字符串 "1" 不包含前导零，是整数 5^0 = 1 的二进制表示。
可以证明 3 是 s 可以分割成的美丽子字符串的最少数目。

示例 3：

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

提示：

  • 1 <= s.length <= 15
  • s[i] 是 ‘0’ 或 ‘1’

解题思路

这道题需要将二进制字符串分割成最少的美丽子字符串，其中美丽字符串必须是5的幂的二进制表示且无前导零。

解题思路：

  1. 预处理5的幂：由于字符串长度最多15位，我们可以预先计算所有可能的5的幂的二进制表示并存储在集合中，便于快速查找。

  2. 动态规划：使用dp[i]表示从位置i到字符串末尾的最少分割数。状态转移方程为：

    • 对于每个位置i，尝试所有可能的子字符串s[i:j]
    • 如果s[i:j]是美丽字符串，则dp[i] = min(dp[i], 1 + dp[j])

  3. 回溯法：也可以使用递归回溯，从前往后尝试所有可能的分割点，记录最小分割数。

  4. 美丽字符串判断：

    • 不能以0开头（除非就是"0"但"0"不是5的幂）
    • 必须是5的幂的二进制表示

由于数据规模较小（长度≤15），两种方法都可行。这里采用动态规划方法，从后往前计算，避免了递归的开销。

推荐解法：动态规划，时间复杂度较低且思路清晰。

代码实现

class Solution {
public:
    int minimumBeautifulSubstrings(string s) {
        int n = s.length();
        
        // 预计算所有可能的5的幂的二进制表示
        unordered_set<string> powers;
        long long power = 1;
        while (power <= (1LL << 15)) {
            string binary = "";
            long long temp = power;
            while (temp > 0) {
                binary = char('0' + temp % 2) + binary;
                temp /= 2;
            }
            powers.insert(binary);
            power *= 5;
        }
        
        // dp[i] 表示从位置i到末尾的最少分割数
        vector<int> dp(n + 1, INT_MAX);
        dp[n] = 0;
        
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == '0') continue; // 不能以0开头
            
            for (int j = i + 1; j <= n; j++) {
                string substr = s.substr(i, j - i);
                if (powers.count(substr) && dp[j] != INT_MAX) {
                    dp[i] = min(dp[i], 1 + dp[j]);
                }
            }
        }
        
        return dp[0] == INT_MAX ? -1 : dp[0];
    }
};

class Solution:
    def minimumBeautifulSubstrings(self, s: str) -> int:
        n = len(s)
        
        # 预计算所有可能的5的幂的二进制表示
        powers = set()
        power = 1
        while power <= (1 << 15):
            powers.add(bin(power)[2:])  # 去掉'0b'前缀
            power *= 5
        
        # dp[i] 表示从位置i到末尾的最少分割数
        dp = [float('inf')] * (n + 1)
        dp[n] = 0
        
        for i in range(n - 1, -1, -1):
            if s[i] == '0':
                continue  # 不能以0开头
            
            for j in range(i + 1, n + 1):
                substr = s[i:j]
                if substr in powers and dp[j] != float('inf'):
                    dp[i] = min(dp[i], 1 + dp[j])
        
        return dp[0] if dp[0] != float('inf') else -1

public class Solution {
    public int MinimumBeautifulSubstrings(string s) {
        int n = s.Length;
        
        // 预计算所有可能的5的幂的二进制表示
        var powers = new HashSet<string>();
        long power = 1;
        while (power <= (1L << 15)) {
            powers.Add(Convert.ToString(power, 2));
            power *= 5;
        }
        
        // dp[i] 表示从位置i到末尾的最少分割数
        int[] dp = new int[n + 1];
        Array.Fill(dp, int.MaxValue);
        dp[n] = 0;
        
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == '0') continue; // 不能以0开头
            
            for (int j = i + 1; j <= n; j++) {
                string substr = s.Substring(i, j - i);
                if (powers.Contains(substr) && dp[j] != int.MaxValue) {
                    dp[i] = Math.Min(dp[i], 1 + dp[j]);
                }
            }
        }
        
        return dp[0] == int.MaxValue ? -1 : dp[0];
    }
}

var minimumBeautifulSubstrings = function(s) {
    const n = s.length;
    
    // 预计算所有可能的5的幂的二进制表示
    const powers = new Set();
    let power = 1;
    while (power <= (1 << 15)) {
        powers.add(power.toString(2));
        power *= 5;
    }
    
    // dp[i] 表示从位置i到末尾的最少分割数
    const dp = new Array(n + 1).fill(Infinity);
    dp[n] = 0;
    
    for (let i = n - 1; i >= 0; i--) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型动态规划解法
时间复杂度O(n²)
空间复杂度O(n + k)

其中 n 是字符串长度，k 是预计算的5的幂的数量（约为 log₅(2¹⁵) ≈ 11）。

相关题目