给你一个二进制字符串 s ,你需要将字符串分割成一个或者多个 子字符串 ,使每个子字符串都是 美丽 的。
如果一个字符串满足以下条件,我们称它是 美丽 的:
它不包含前导 0 。
它是 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 <= 15
s[i] 要么是 ‘0’ 要么是 ‘1’ 。
记忆化搜索
// 预处理 2**15 以内的 5 的幂的二进制表示
vector<string> pow5 = {"1", "101", "11001", "1111101", "1001110001", "110000110101", "11110100001001"
};class Solution {
public:int minimumBeautifulSubstrings(string s) {int n = s.size();vector<int> memo(n, -1);function<int(int)> dfs = [&](int i) -> int{if(i == n) return 0;if(memo[i] != -1) return memo[i];if(s[i] == '0') return INT_MAX;int res = INT_MAX;for(string &t : pow5){if(i + t.size() > n) break;if(s.substr(i, t.size()) == t){int sub_res = dfs(i + t.size());if(sub_res != INT_MAX){res = min(res, sub_res + 1);}}}return memo[i] = res;};return dfs(0) == INT_MAX ? -1 : dfs(0);}
};
时间复杂度:O(N*K)
空间复杂度: O(N)
我们首先先找出预处理 2^15 以内的 5 的幂的二进制表示,记录在容器pow5中。memo是记忆化用。最重要的是回溯的思路,我们定义dfs(i)的含义是从第i个字符后的字符串被分割成最少的美丽子字符串的个数,所以我们可以思考,我们从第0个字符开始,举个例子,如果找到了一个5的二进制表示101,那么也就是说,在这个回溯中,我们dfs(0)也就是dfs(3)+1,然后dfs(3)会继续往上回溯。那么既然使用了回溯,就要知道在回溯的末端我们该如何处理,在回溯末端我们刚好可以分割完字符串为美丽数组,那么就返回0,也就代表这个回溯的过程是可行的。如果无法分割,还有剩下的字符,那么res依旧为INT_MAX,也就是代表该回溯过程是不可行的。最后返回dfs(0)即可。