Medium

题目描述

给定整数 zero、one、low 和 high，我们可以从空字符串开始构造字符串，然后在每一步执行以下操作之一：

  • 添加字符 '0' 零次。
  • 添加字符 '1' 一次。

此操作可以执行任意次数。

一个好字符串是通过上述过程构造的字符串，其长度在 low 和 high（包括）之间。

返回可以构造的满足这些属性的不同好字符串的数量。由于答案可能很大，返回结果对 10^9 + 7 取模。

示例 1：

输入：low = 3, high = 3, zero = 1, one = 1
输出：8
解释：
一个可能的有效好字符串是 "011"。
它可以按如下方式构造："" -> "0" -> "01" -> "011"。
从 "000" 到 "111" 的所有二进制字符串在此示例中都是好字符串。

示例 2：

输入：low = 2, high = 3, zero = 1, one = 2
输出：5
解释：好字符串有 "00", "11", "000", "110", 和 "011"。

约束条件：

  • 1 <= low <= high <= 10^5
  • 1 <= zero, one <= low

解题思路

这是一个典型的动态规划问题。我们需要计算长度在 [low, high] 范围内的字符串方案数。

核心思路：

  1. 定义 dp[i] 表示构造长度为 i 的字符串的方案数

  2. 状态转移方程：

    • dp[i] = dp[i-zero] + dp[i-one]
    • 意思是长度为 i 的字符串可以由长度为 i-zero 的字符串添加 zero 个 '0' 得到，或由长度为 i-one 的字符串添加 one 个 '1' 得到

  3. 初始状态：dp[0] = 1（空字符串有一种构造方案）

  4. 最终答案：sum(dp[low:high+1])

优化考虑：

  • 由于只关心长度在 [low, high] 范围内的方案数，我们可以边计算边累加结果
  • 使用取模运算防止整数溢出

时间复杂度： O(high)，需要计算从 0 到 high 的所有 dp 值 空间复杂度： O(high)，需要存储 dp 数组

代码实现

class Solution {
public:
    int countGoodStrings(int low, int high, int zero, int one) {
        const int MOD = 1e9 + 7;
        vector<int> dp(high + 1, 0);
        dp[0] = 1;
        
        int result = 0;
        for (int i = 1; i <= high; i++) {
            if (i >= zero) {
                dp[i] = (dp[i] + dp[i - zero]) % MOD;
            }
            if (i >= one) {
                dp[i] = (dp[i] + dp[i - one]) % MOD;
            }
            if (i >= low) {
                result = (result + dp[i]) % MOD;
            }
        }
        
        return result;
    }
};

class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
        MOD = 10**9 + 7
        dp = [0] * (high + 1)
        dp[0] = 1
        
        result = 0
        for i in range(1, high + 1):
            if i >= zero:
                dp[i] = (dp[i] + dp[i - zero]) % MOD
            if i >= one:
                dp[i] = (dp[i] + dp[i - one]) % MOD
            if i >= low:
                result = (result + dp[i]) % MOD
        
        return result

public class Solution {
    public int CountGoodStrings(int low, int high, int zero, int one) {
        const int MOD = 1000000007;
        int[] dp = new int[high + 1];
        dp[0] = 1;
        
        int result = 0;
        for (int i = 1; i <= high; i++) {
            if (i >= zero) {
                dp[i] = (dp[i] + dp[i - zero]) % MOD;
            }
            if (i >= one) {
                dp[i] = (dp[i] + dp[i - one]) % MOD;
            }
            if (i >= low) {
                result = (result + dp[i]) % MOD;
            }
        }
        
        return result;
    }
}

var countGoodStrings = function(low, high, zero, one) {
    const MOD = 1000000007;
    const dp = new Array(high + 1).fill(0);
    dp[0] = 1;
    
    let result = 0;
    for (let i = 1; i <= high; i++) {
        if (i >= zero) {
            dp[i] = (dp[i] + dp[i - zero]) % MOD;
        }
        if (i >= one) {
            dp[i] = (dp[i] + dp[i - one]) % MOD;
        }
        if (i >= low) {
            result = (result + dp[i]) % MOD;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(high)需要遍历从 1 到 high 的所有长度
空间复杂度O(high)需要 dp 数组存储每个长度的方案数

相关题目