题目描述
给你一个二进制字符串 s
,你需要将字符串分割成一个或者多个 子字符串,使每个子字符串都是 美丽 的。
如果一个字符串满足以下条件,我们称它是 美丽 的:
- 它不包含前导
0
。 - 它是
5
的幂的 二进制 表示。
请你返回分割后的子字符串的 最少 数目。如果无法将字符串 s
分割成美丽子字符串,请你返回 -1
。
子字符串是一个字符串中一段连续的字符序列。
样例
输入:s = "1011"
输出:2
解释:我们可以将输入字符串分成 ["101", "1"] 。
- 字符串 "101" 不包含前导 0 ,且它是整数 51 = 5 的二进制表示。
- 字符串 "1" 不包含前导 0 ,且它是整数 50 = 1 的二进制表示。
最少可以将 s 分成 2 个美丽子字符串。
输入:s = "111"
输出:3
解释:我们可以将输入字符串分成 ["1", "1", "1"] 。
- 字符串 "1" 不包含前导 0 ,且它是整数 50 = 1 的二进制表示。
最少可以将 s 分成 3 个美丽子字符串。
输入:s = "0"
输出:-1
解释:无法将给定字符串分成任何美丽子字符串。
限制
1 <= s.length <= 15
s[i]
要么是'0'
要么是'1'
。
算法
(递归回溯) $O(2^n)$
- 递归回溯尝试在每个位置进行分隔,找到合法的分割方式下的最小分隔次数。
时间复杂度
- 每个位置都可能被尝试分隔一次,故时间复杂度为 $O(2^n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储递归的系统栈。
C++ 代码
class Solution {
private:
int ans;
bool check(int x) {
return x == 1 || x == 5 || x == 25 || x == 125 ||
x == 625 || x == 3125 || x == 15625;
}
void solve(int i, int x, int cnt, const string &s) {
if (x == 0)
return;
if (i == s.size()) {
if (check(x))
ans = min(ans, cnt);
return;
}
solve(i + 1, (x << 1) | (s[i] - '0'), cnt, s);
if (check(x))
solve(i + 1, s[i] - '0', cnt + 1, s);
}
public:
int minimumBeautifulSubstrings(string s) {
ans = INT_MAX;
solve(1, s[0] - '0', 1, s);
if (ans == INT_MAX)
return -1;
return ans;
}
};