Question

2466. 统计构造好字符串的方案数

English Version

题目描述

给你整数 zero ，one ，low 和 high ，我们从空字符串开始构造一个字符串，每一步执行下面操作中的一种：

• 将 '0' 在字符串末尾添加 zero  次。
• 将 '1' 在字符串末尾添加 one 次。

以上操作可以执行任意次。

如果通过以上过程得到一个 长度 在 low 和 high 之间（包含上下边界）的字符串，那么这个字符串我们称为 好 字符串。

请你返回满足以上要求的 不同 好字符串数目。由于答案可能很大，请将结果对 109 + 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 <= 105
• 1 <= zero, one <= low

解法

方法一：记忆化搜索

我们设计一个函数 $dfs(i)$ 表示从第 $i$ 位开始构造的好字符串的个数，答案即为 $dfs(0)$。

函数 $dfs(i)$ 的计算过程如下：

• 如果 $i \gt high$，返回 $0$；
• 如果 $ low \leq i \leq high$，答案累加 $1$，然后 $i$ 之后既可以添加 zero 个 $0$，也可以添加 one 个 $1$，因此答案累加上 $dfs(i + zero) + dfs(i + one)$。

过程中，我们需要对答案取模，并且可以使用记忆化搜索减少重复计算。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n = high$。

class Solution:
  def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
    @cache
    def dfs(i):
      if i > high:
        return 0
      ans = 0
      if low <= i <= high:
        ans += 1
      ans += dfs(i + zero) + dfs(i + one)
      return ans % mod

    mod = 10**9 + 7
    return dfs(0)

class Solution {
  private static final int MOD = (int) 1e9 + 7;
  private int[] f;
  private int lo;
  private int hi;
  private int zero;
  private int one;

  public int countGoodStrings(int low, int high, int zero, int one) {
    f = new int[high + 1];
    Arrays.fill(f, -1);
    lo = low;
    hi = high;
    this.zero = zero;
    this.one = one;
    return dfs(0);
  }

  private int dfs(int i) {
    if (i > hi) {
      return 0;
    }
    if (f[i] != -1) {
      return f[i];
    }
    long ans = 0;
    if (i >= lo && i <= hi) {
      ++ans;
    }
    ans += dfs(i + zero) + dfs(i + one);
    ans %= MOD;
    f[i] = (int) ans;
    return f[i];
  }
}

class Solution {
public:
  const int mod = 1e9 + 7;

  int countGoodStrings(int low, int high, int zero, int one) {
    vector<int> f(high + 1, -1);
    function<int(int)> dfs = [&](int i) -> int {
      if (i > high) return 0;
      if (f[i] != -1) return f[i];
      long ans = i >= low && i <= high;
      ans += dfs(i + zero) + dfs(i + one);
      ans %= mod;
      f[i] = ans;
      return ans;
    };
    return dfs(0);
  }
};

func countGoodStrings(low int, high int, zero int, one int) int {
  f := make([]int, high+1)
  for i := range f {
    f[i] = -1
  }
  const mod int = 1e9 + 7
  var dfs func(i int) int
  dfs = func(i int) int {
    if i > high {
      return 0
    }
    if f[i] != -1 {
      return f[i]
    }
    ans := 0
    if i >= low && i <= high {
      ans++
    }
    ans += dfs(i+zero) + dfs(i+one)
    ans %= mod
    f[i] = ans
    return ans
  }
  return dfs(0)
}