将字符串分割成值不超过 K 的子字符串

标签: 贪心 字符串 动态规划

难度: Medium

给你一个字符串 s ，它每一位都是 1 到 9 之间的数字组成，同时给你一个整数 k 。

如果一个字符串 s 的分割满足以下条件，我们称它是一个 好 分割：

  • s 中每个数位 恰好 属于一个子字符串。
  • 每个子字符串的值都小于等于 k 。

请你返回 s 所有的 好 分割中，子字符串的 最少 数目。如果不存在 s 的 好 分割，返回 -1 。

注意：

  • 一个字符串的 值 是这个字符串对应的整数。比方说，"123" 的值为 123 ，"1" 的值是 1 。
  • 子字符串 是字符串中一段连续的字符序列。

示例 1：

输入：s = "165462", k = 60
输出：4
解释：我们将字符串分割成子字符串 "16" ，"54" ，"6" 和 "2" 。每个子字符串的值都小于等于 k = 60 。
不存在小于 4 个子字符串的好分割。

示例 2：

输入：s = "238182", k = 5
输出：-1
解释：这个字符串不存在好分割。

提示：

  • 1 <= s.length <= 105
  • s[i] 是 '1' 到 '9' 之间的数字。
  • 1 <= k <= 109

Submission

运行时间: 44 ms

内存: 16.5 MB

class Solution:
    def minimumPartition(self, s: str, k: int) -> int:
        t =k
        siz = 0
        n = len(s)
        while t !=0:
            siz +=1
            t //=10
        if siz == 1:
            for x in s:
                if int(x)>k:
                    return -1
            return n
        ans = 0
        l= 0
        while l < n:
            if int(s[l:l+siz]) <=k:
                l += siz
                ans +=1
            else:
                if int(s[l:(l + siz -1)]) <=k:
                    l += siz -1
                    ans +=1
                else:
                    return -1
        return ans

Explain

此题解采用了贪心算法，目标是最小化分割子字符串的数量，同时每个子字符串的整数值不超过给定的k。首先，根据k的大小决定最大可能的子字符串长度（siz），这是通过计算k可以有多少位数来确定的。例如，如果k是60，则最大可能的子字符串长度是2，因为60是两位数。接着，根据siz尝试从字符串s的左侧开始尽可能地切分长度为siz的子字符串，同时确保每个子字符串的数值不超过k。如果在某个位置上无法进行这样的切分，尝试减少一个字符，使长度变为siz-1，再次检查是否满足条件。如果仍不满足条件，则返回-1，表示无法进行好分割。这个过程重复直到字符串的末尾。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def minimumPartition(self, s: str, k: int) -> int:
        # 计算k的位数，决定子字符串的最大长度
        t = k
        siz = 0
        while t != 0:
            siz += 1
            t //= 10
        # 如果k的位数为1，检查s中每个数字是否都小于等于k
        if siz == 1:
            for x in s:
                if int(x) > k:
                    return -1
            return len(s)
        ans = 0  # 初始化最少分割次数
        l = 0  # 初始化当前检查的位置
        n = len(s)  # 获取s的长度
        while l < n:
            # 尝试切分长度为siz的子字符串
            if int(s[l:l+siz]) <= k:
                l += siz
                ans += 1
            else:
                # 尝试切分长度为siz-1的子字符串
                if int(s[l:(l + siz - 1)]) <= k:
                    l += siz - 1
                    ans += 1
                else:
                    return -1  # 如果两种情况都不满足，返回-1
        return ans  # 返回最少分割次数

Explore

在设计贪心算法时，我们首先通过确定k可以表示为多少位数来估算可能的子字符串的最大长度。这种方法简化了问题，因为如果我们考虑每个可能的数字组合，复杂度将显著增加。此外，只有当子字符串的长度不超过k的位数时，其数值才有可能不超过k。这是一种保守的估计，旨在快速确定一个安全的上界，从而避免不必要的复杂性。

当k的位数为1时，意味着k的值从0到9。这种情况下，字符串s中的每个字符应该是一个0到9的数字，且每个字符独立为一个子字符串。只要检查每个字符是否不超过k即可。因为每个字符都是独立的数字，所以这种方法在所有情况下都是有效的，前提是s只包含数字字符。

如果子字符串的起始位置加上siz超过了字符串s的长度，此时不能形成一个完整的siz长度的子字符串。在这种情况下，我们应该考虑从当前位置到字符串结尾的所有字符作为一个子字符串，并检查其值是否不超过k。如果超过k，则无法进行有效的分割，并应返回-1。否则，这将是最后一个子字符串，并且分割结束。

尝试减少一个字符的策略基于贪心算法的思想，即尽可能地使用最长的子字符串来减少总的分割次数。虽然这种策略可能在某些情况下未能找到所有可能的分割方式，但它保证了如果存在一种有效的分割方法，该方法将最小化分割数量。如果减少字符后仍不满足条件，则可能需要更复杂的回溯或动态规划方法来探索所有可能的分割策略。