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

Given a binary string s, partition the string into one or more substrings such that each substring is beautiful.

A string is beautiful if:

• It doesn't contain leading zeros.
• It's the binary representation of a number that is a power of 5.

Return the minimum number of substrings in such partition. If it is impossible to partition the string s into beautiful substrings, return -1.

A substring is a contiguous sequence of characters in a string.

 

Example 1:

Input: s = "1011"
Output: 2
Explanation: We can paritition the given string into ["101", "1"].
- The string "101" does not contain leading zeros and is the binary representation of integer 51 = 5.
- The string "1" does not contain leading zeros and is the binary representation of integer 50 = 1.
It can be shown that 2 is the minimum number of beautiful substrings that s can be partitioned into.

Example 2:

Input: s = "111"
Output: 3
Explanation: We can paritition the given string into ["1", "1", "1"].
- The string "1" does not contain leading zeros and is the binary representation of integer 50 = 1.
It can be shown that 3 is the minimum number of beautiful substrings that s can be partitioned into.

Example 3:

Input: s = "0"
Output: -1
Explanation: We can not partition the given string into beautiful substrings.

 

Constraints:

• 1 <= s.length <= 15
• s[i] is either '0' or '1'.

/*
 * 题目思路：
 * 1. 使用Java Stream API来进行动态规划求解。
 * 2. 遍历字符串的所有子串，判断是否为美丽字符串。
 * 3. 使用一个Boolean数组记录某个子串是否为美丽字符串，然后利用IntStream更新dp数组。
 */
import java.util.stream.IntStream;
public class BeautifulSubstringStream {
    public static int minBeautifulSubstrings(String s) {
        int n = s.length();
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        Boolean[] isBeautiful = new Boolean[n + 1];
        Arrays.fill(isBeautiful, false);
        for (int i = 1; i <= n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                String sub = s.substring(j, i);
                isBeautiful[i] = isBeautiful(sub);
            }
        }
        IntStream.rangeClosed(1, n).forEach(i -> {
            if (isBeautiful[i]) {
                IntStream.range(0, i).forEach(j -> {
                    if (dp[j] != Integer.MAX_VALUE) {
                        dp[i] = Math.min(dp[i], dp[j] + 1);
                    }
                });
            }
        });
        return dp[n] == Integer.MAX_VALUE ? -1 : dp[n];
    }
    private static boolean isBeautiful(String s) {
        if (s.charAt(0) == '0') return false;
        long num = Long.parseLong(s, 2);
        while (num % 5 == 0) num /= 5;
        return num == 1;
    }
}

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

O(7^n)

O(n)