[LeetCode] 2466. Count Ways To Build Good Strings (Python)

 

난이도: Medium

 

문제 설명

---

Given the integers zero, one, low, and high, we can construct a string by starting with an empty string, and then at each step perform either of the following:

• Append the character '0' zero times.
• Append the character '1' one times.

This can be performed any number of times.

A good string is a string constructed by the above process having a length between low and high (inclusive).

Return the number of different good strings that can be constructed satisfying these properties. Since the answer can be large, return it modulo 10^9 + 7.

 

문제 예제

---

Example 1:

Input: low = 3, high = 3, zero = 1, one = 1
Output: 8
Explanation:
One possible valid good string is "011".
It can be constructed as follows: "" -> "0" -> "01" -> "011".
All binary strings from "000" to "111" are good strings in this example.

Example 2:

Input: low = 2, high = 3, zero = 1, one = 2
Output: 5
Explanation: The good strings are "00", "11", "000", "110", and "011".

 

제한 사항

---

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

 

✏️Solution(솔루션)

class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
        mod = 10**9 + 7
        dp = [0 for _ in range(high+1)]
        dp[0] = 1
        answer = 0

        for i in range(1, high+1):
            dp[i] = dp[i-zero] + dp[i-one]
            dp[i] %= mod
            
            if low<=i<=high:
                answer += dp[i]
        
        return answer % mod

 

high까지 만들 수 있는 string의 길이를 구하기 위해 high+1 길이의 0으로 채운 dp라는 리스트를 만들었다.

 

각 dp[i]에는 길이가 i인 문자열의 개수를 저장한다.

처음에 dp[0]은 1로 설정했는데, 이는 길이가 0인 문자열("")의 개수를 나타낸다.

 

다음으로 1부터 high까지 도는 반복문을 설정하고, 길이가 i인 문자열을 만들기 위한 경우의 수를 구한다.

 

이 경우의 수는 길이가 i-zero인 문자열의 경우의 수와  i-one인 문자열의 경우의 수를 더하면 된다. 

 

그리고 그 값이 클 수 있으니, 문제 설명에 나와있듯이 mod를 통해 값을 줄여준다.

 

그리고 low<= i <=high 를 만족하는 dp[i]의 값을 더해 정답으로 return하였다.

 

 

---

2466. Count Ways To Build Good Strings