跳转至

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

题目描述

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

解法

方法一：记忆化搜索

题目中需要判断一个字符串是否是 $5$ 的幂的二进制表示，因此，我们不妨先预处理出所有 $5$ 的幂的数字，记录在哈希表 $ss$ 中。

接下来，我们设计一个函数 $dfs(i)$，表示从字符串 $s$ 的第 $i$ 个字符开始，到字符串末尾的最少分割次数。那么答案就是 $dfs(0)$。

函数 $dfs(i)$ 的计算方法如下：

  • 如果 $i \geq n$，表示已经处理完了所有字符，那么答案就是 $0$；
  • 如果 $s[i] = 0$，表示当前字符串包含前导 $0$，不符合美丽字符串的定义，因此答案是无穷大；
  • 否则，我们从 $i$ 开始枚举子字符串的结束位置 $j$，用 $x$ 表示子字符串 $s[i..j]$ 的十进制值，如果 $x$ 在哈希表 $ss$ 中，那么我们就可以将 $s[i..j]$ 作为一个美丽子字符串，此时答案就是 $1 + dfs(j + 1)$。我们需要枚举所有可能的 $j$，并取所有答案中的最小值。

为了避免重复计算，我们可以使用记忆化搜索的方法。

在主函数中，我们首先预处理出所有 $5$ 的幂的数字，然后调用 $dfs(0)$，如果返回值为无穷大，那么说明无法将字符串 $s$ 分割成美丽子字符串，答案返回 $-1$，否则返回 $dfs(0)$ 的值。

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。其中 $n$ 是字符串 $s$ 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def minimumBeautifulSubstrings(self, s: str) -> int:
        @cache
        def dfs(i: int) -> int:
            if i >= n:
                return 0
            if s[i] == "0":
                return inf
            x = 0
            ans = inf
            for j in range(i, n):
                x = x << 1 | int(s[j])
                if x in ss:
                    ans = min(ans, 1 + dfs(j + 1))
            return ans

        n = len(s)
        x = 1
        ss = {x}
        for i in range(n):
            x *= 5
            ss.add(x)
        ans = dfs(0)
        return -1 if ans == inf else ans

 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
34
35
36
37
38
39
40
class Solution {
    private Integer[] f;
    private String s;
    private Set<Long> ss = new HashSet<>();
    private int n;

    public int minimumBeautifulSubstrings(String s) {
        n = s.length();
        this.s = s;
        f = new Integer[n];
        long x = 1;
        for (int i = 0; i <= n; ++i) {
            ss.add(x);
            x *= 5;
        }
        int ans = dfs(0);
        return ans > n ? -1 : ans;
    }

    private int dfs(int i) {
        if (i >= n) {
            return 0;
        }
        if (s.charAt(i) == '0') {
            return n + 1;
        }
        if (f[i] != null) {
            return f[i];
        }
        long x = 0;
        int ans = n + 1;
        for (int j = i; j < n; ++j) {
            x = x << 1 | (s.charAt(j) - '0');
            if (ss.contains(x)) {
                ans = Math.min(ans, 1 + dfs(j + 1));
            }
        }
        return f[i] = ans;
    }
}

 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
34
35
36
class Solution {
public:
    int minimumBeautifulSubstrings(string s) {
        unordered_set<long long> ss;
        int n = s.size();
        long long x = 1;
        for (int i = 0; i <= n; ++i) {
            ss.insert(x);
            x *= 5;
        }
        int f[n];
        memset(f, -1, sizeof(f));
        function<int(int)> dfs = [&](int i) {
            if (i >= n) {
                return 0;
            }
            if (s[i] == '0') {
                return n + 1;
            }
            if (f[i] != -1) {
                return f[i];
            }
            long long x = 0;
            int ans = n + 1;
            for (int j = i; j < n; ++j) {
                x = x << 1 | (s[j] - '0');
                if (ss.count(x)) {
                    ans = min(ans, 1 + dfs(j + 1));
                }
            }
            return f[i] = ans;
        };
        int ans = dfs(0);
        return ans > n ? -1 : ans;
    }
};

 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
34
35
36
37
func minimumBeautifulSubstrings(s string) int {
    ss := map[int]bool{}
    n := len(s)
    x := 1
    f := make([]int, n+1)
    for i := 0; i <= n; i++ {
        ss[x] = true
        x *= 5
        f[i] = -1
    }
    var dfs func(int) int
    dfs = func(i int) int {
        if i >= n {
            return 0
        }
        if s[i] == '0' {
            return n + 1
        }
        if f[i] != -1 {
            return f[i]
        }
        f[i] = n + 1
        x := 0
        for j := i; j < n; j++ {
            x = x<<1 | int(s[j]-'0')
            if ss[x] {
                f[i] = min(f[i], 1+dfs(j+1))
            }
        }
        return f[i]
    }
    ans := dfs(0)
    if ans > n {
        return -1
    }
    return ans
}

 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
function minimumBeautifulSubstrings(s: string): number {
    const ss: Set<number> = new Set();
    const n = s.length;
    const f: number[] = new Array(n).fill(-1);
    for (let i = 0, x = 1; i <= n; ++i) {
        ss.add(x);
        x *= 5;
    }
    const dfs = (i: number): number => {
        if (i === n) {
            return 0;
        }
        if (s[i] === '0') {
            return n + 1;
        }
        if (f[i] !== -1) {
            return f[i];
        }
        f[i] = n + 1;
        for (let j = i, x = 0; j < n; ++j) {
            x = (x << 1) | (s[j] === '1' ? 1 : 0);
            if (ss.has(x)) {
                f[i] = Math.min(f[i], 1 + dfs(j + 1));
            }
        }
        return f[i];
    };
    const ans = dfs(0);
    return ans > n ? -1 : ans;
}

评论