2466. Count Ways To Build Good Strings

link

Backtrack

class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:

        MOD = 10 ** 9 + 7

        @cache
        def backtrack(c):
            if c > high:
                return 0
            
            res = 0

            if c >= low:
                res += 1

            return(res + backtrack(c+zero) + backtrack(c+one))% MOD


        return backtrack(0) % MOD

DP

class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:

        dp = [0] * (high + 1)

        dp[0] = 1

        for i in range(1, high + 1):
            if dp[i - zero] != 0:
                dp[i] += dp[i - zero]
            if dp[i - one] != 0:
                dp[i] += dp[i - one]

            dp[i] = dp[i] % (10 ** 9 + 7)
        
        return sum(dp[low:high+1]) % (10 ** 9 + 7)