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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:27 2023-09-13 16:06:27 Updated    

给你一个二进制字符串 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' 。

下午两点【b站@灵茶山艾府】 直播讲题，欢迎关注！

前置知识：动态规划入门

详见 动态规划入门：从记忆化搜索到递推【基础算法精讲 17】

思路

由于字符串的长度为 n，所以二进制的值是低于 2^n 的。那么可以预处理 2^n 以内的 5 的幂的二进制表示，记作 pow}_5。由于测试数据很多，可以用全局变量，预处理 2^{15 以内的 5 的幂（有 7 个）。

定义 dfs}(i) 表示划分从 s[i] 开始的后缀，最少要划分成多少段。

枚举 pow}_5 中的字符串 t，设其长度为 m，如果从 s[i] 到 s[i+m-1] 与 t 相等，那么有

\textit{dfs}(i) = \textit{dfs}(i+m) + 1

所有情况取最小值。

如果 s[i]=\texttt{0，或者不存在这样的 t，那么 dfs}(i)=\infty。

递归边界：dfs}(n)=0。

递归入口：dfs}(0)。

注意在比较字符串时，由于 pow}_5 中字符串的公共前缀很短，很容易就失配了，所以除了匹配上的那次是 \mathcal{O}(n) 的，其余匹配都可以视作是 \mathcal{O}(1) 的。

[sol-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 预处理 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

按照视频中的做法，1:1 翻译成递推。

倒着遍历的好处是方便判断是否有前导零。

[sol-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 预处理 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
[sol-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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 }

复杂度分析

  • 时间复杂度：\mathcal{O}(n^2)，其中 n 为 s 的长度。动态规划的时间复杂度 = 状态个数 \times 单个状态的计算时间。本题中状态个数等于 \mathcal{O}(n)，单个状态的计算时间为 \mathcal{O}(n)，所以动态规划的时间复杂度为 \mathcal{O}(n^2)。注意在比较字符串时，由于 pow}_5 中字符串的公共前缀很短，很容易就失配了，所以除了匹配上的那次是 \mathcal{O}(n) 的，其余匹配都可以视作是 \mathcal{O}(1) 的。
  • 空间复杂度：\mathcal{O}(n)。
 Comments
On this page
2767-将字符串分割为最少的美丽子字符串
  1. 前置知识：动态规划入门
  2. 思路