class Solution {
public:
int minimumBeautifulSubstrings(string s) {
}
};
6923. 将字符串分割为最少的美丽子字符串
给你一个二进制字符串 s ，你需要将字符串分割成一个或者多个 子字符串 ，使每个子字符串都是 美丽 的。
如果一个字符串满足以下条件，我们称它是 美丽 的：
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' 。原站题解
java 解法, 执行用时: 2 ms, 内存消耗: 41 MB, 提交时间: 2023-07-10 09:41:06
class Solution {
public final static String[] fiveN;
static{
fiveN = new String[7];
fiveN[0] = "1";
fiveN[1] = "101";
fiveN[2] = "11001";
fiveN[3] = "1111101";
fiveN[4] = "1001110001";
fiveN[5] = "110000110101";
fiveN[6] = "11110100001001";
}
/**
* 参考0x3f大佬的题解
* dp[i]表示从i开始最少分成多少段
* 状态转移 ： dp[i] = dp[i + m] + 1; ( m 为 5 的幂的二进制的长度)
*/
public int minimumBeautifulSubstrings(String s) {
int n = s.length();
int[] dp = new int[n + 1];
dp[n] = 0;
for(int i = n - 1; i >= 0; i--) {
dp[i] = 16;
if(s.charAt(i) == '0') continue;
for(String fivesn : fiveN) {
if(i + fivesn.length() > n) break;
if(s.substring(i, i + fivesn.length()).equals(fivesn)) {
dp[i] = Math.min(dp[i], dp[i + fivesn.length()] + 1);
}
}
}
return dp[0] > n ? -1 : dp[0];
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2023-07-10 09:39:38
var pow5 []string
func init() {
// 预处理 2**15 以内的 5 的幂
for p5 := 1; p5 < 1<<15; p5 *= 5 {
pow5 = append(pow5, strconv.FormatUint(uint64(p5), 2))
}
}
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 }
python3 解法, 执行用时: 56 ms, 内存消耗: 16 MB, 提交时间: 2023-07-10 09:38:54
'''
递推
'''
# 预处理 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
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
python3 解法, 执行用时: 52 ms, 内存消耗: 16.2 MB, 提交时间: 2023-07-10 09:37:19
'''
记忆化搜索
dfs(i): 划分从s[i]开始的后缀，最少要划分多少段。
'''
# 预处理 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