Medium

题目描述

给你一个由数字 1 到 9 组成的字符串 s 和一个整数 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 <= 10^5
  • s[i] 是从 '1' 到 '9' 的数字
  • 1 <= k <= 10^9

解题思路

这道题可以使用贪心算法来解决。

核心思路： 为了使分割的子字符串数目最少，我们应该尽可能让每个子字符串都尽可能长，也就是说在满足值不超过 k 的前提下，尽可能多地包含字符。

算法步骤：

  1. 从左到右遍历字符串，维护当前子字符串的数值
  2. 对于每个位置，尝试将当前字符加入当前子字符串
  3. 如果加入后的值仍然 ≤ k，则继续扩展
  4. 如果加入后的值 > k，则需要开始一个新的子字符串
  5. 特别注意：如果单个字符的值就 > k，则无法形成好分割，返回 -1

贪心策略的正确性： 由于我们的目标是最小化分割数，每次都尽可能地延长当前子字符串是最优的选择。如果在某个位置提前分割，只会增加总的分割数而不会减少。

时间复杂度优化： 由于字符串可能很长，直接用字符串转整数可能会溢出。我们可以在计算过程中及时判断是否会超过 k，避免大数运算。

代码实现

class Solution {
public:
    int minimumPartition(string s, int k) {
        int n = s.length();
        int count = 0;
        int i = 0;
        
        while (i < n) {
            long long current = 0;
            int start = i;
            
            // 尝试构建尽可能长的子字符串
            while (i < n) {
                int digit = s[i] - '0';
                // 检查是否会溢出或超过k
                if (current > (k - digit) / 10) {
                    break;
                }
                current = current * 10 + digit;
                if (current > k) {
                    break;
                }
                i++;
            }
            
            // 如果没有前进（单个字符就超过k），返回-1
            if (i == start) {
                return -1;
            }
            
            count++;
        }
        
        return count;
    }
};

class Solution:
    def minimumPartition(self, s: str, k: int) -> int:
        n = len(s)
        count = 0
        i = 0
        
        while i < n:
            current = 0
            start = i
            
            # 尝试构建尽可能长的子字符串
            while i < n:
                digit = int(s[i])
                # 检查是否会超过k
                if current > (k - digit) // 10:
                    break
                current = current * 10 + digit
                if current > k:
                    break
                i += 1
            
            # 如果没有前进（单个字符就超过k），返回-1
            if i == start:
                return -1
            
            count += 1
        
        return count

public class Solution {
    public int MinimumPartition(string s, int k) {
        int n = s.Length;
        int count = 0;
        int i = 0;
        
        while (i < n) {
            long current = 0;
            int start = i;
            
            // 尝试构建尽可能长的子字符串
            while (i < n) {
                int digit = s[i] - '0';
                // 检查是否会溢出或超过k
                if (current > (k - digit) / 10) {
                    break;
                }
                current = current * 10 + digit;
                if (current > k) {
                    break;
                }
                i++;
            }
            
            // 如果没有前进（单个字符就超过k），返回-1
            if (i == start) {
                return -1;
            }
            
            count++;
        }
        
        return count;
    }
}

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var minimumPartition = function(s, k) {
    let count = 0;
    let i = 0;
    
    while (i < s.length) {
        let current = 0;
        let j = i;
        
        while (j < s.length) {
            let newValue = current * 10 + parseInt(s[j]);
            if (newValue > k) {
                break;
            }
            current = newValue;
            j++;
        }
        
        if (j === i) {
            return -1;
        }
        
        count++;
        i = j;
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n)
空间复杂度O(1)

说明：

  • 时间复杂度： 每个字符最多被访问一次，总体为 O(n)
  • 空间复杂度： 只使用了常数个变量，为 O(1)