Nov 10, 2024 · Dec 16, 2023 · Jan 16, 2024 · Jan 16, 2024 · Jan 16, 2024 · Jan 16, 2024
diff --git a/python/0338-counting-bits.py b/python/0338-counting-bits.py
                offset = i
            dp[i] = 1 + dp[i - offset]
        return dp

 # Another dp solution
 class Solution2:
    def countBits(self, n: int) -> List[int]:
        res = [0] * (n + 1)
        for i in range(1, n + 1):
            if i % 2 == 1:
                res[i] = res[i - 1] + 1
            else:
                res[i] = res[i // 2]
        return res
 # This solution is based on the division of odd and even numbers.
 # I think it's easier to understand.
 # This is my full solution, covering the details: https://leetcode.com/problems/counting-bits/solutions/4411054/odd-and-even-numbers-a-easier-to-understanding-way-of-dp/
diff --git a/python/1397-find-all-good-strings-i.py b/python/1397-find-all-good-strings-i.py
 class Solution:
    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
        a = ord('a')
        z = ord('z')

        arr_e = list(map(ord, evil))
        len_e = len(evil)
        next = [0] * len_e

        for i in range(1, len_e):
            j = next[i - 1]
            while j > 0 and evil[i] != evil[j]:
                j = next[j - 1]
            if evil[i] == evil[j]:
                next[i] = j + 1

        def good(s):
            arr = list(map(ord, s))
            len_a = len(arr)

            @cache
            def f(i, skip, reach, e):
                if e == len_e:
                    return 0
                if i == len_a:
                    return 0 if skip else 1

                limit = arr[i] if reach else z
                ans = 0

                if skip:
                    ans += f(i + 1, True, False, 0)

                for c in range(a, limit + 1):
                    ee = e
                    while ee > 0 and arr_e[ee] != c:
                        ee = next[ee - 1]

                    if arr_e[ee] == c:
                        ee += 1

                    ans += f(i + 1, False, reach and c == limit, ee)

                return ans % int(1e9 + 7)

            return f(0, True, True, 0)

        return (good(s2) - good(s1) + int(evil not in s1)) % int(1e9 + 7)
Original file line number	Diff line number	Diff line change
Expand Up		@@ -8,3 +8,17 @@ def countBits(self, n: int) -> List[int]:
		offset = i
		dp[i] = 1 + dp[i - offset]
		return dp

		# Another dp solution
		class Solution2:
		def countBits(self, n: int) -> List[int]:
		res = [0] * (n + 1)
		for i in range(1, n + 1):
		if i % 2 == 1:
		res[i] = res[i - 1] + 1
		else:
		res[i] = res[i // 2]
		return res
		# This solution is based on the division of odd and even numbers.
		# I think it's easier to understand.
		# This is my full solution, covering the details: https://leetcode.com/problems/counting-bits/solutions/4411054/odd-and-even-numbers-a-easier-to-understanding-way-of-dp/
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,48 @@
		class Solution:
		def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
		a = ord('a')
		z = ord('z')

		arr_e = list(map(ord, evil))
		len_e = len(evil)
		next = [0] * len_e

		for i in range(1, len_e):
		j = next[i - 1]
		while j > 0 and evil[i] != evil[j]:
		j = next[j - 1]
		if evil[i] == evil[j]:
		next[i] = j + 1

		def good(s):
		arr = list(map(ord, s))
		len_a = len(arr)

		@cache
		def f(i, skip, reach, e):
		if e == len_e:
		return 0
		if i == len_a:
		return 0 if skip else 1

		limit = arr[i] if reach else z
		ans = 0

		if skip:
		ans += f(i + 1, True, False, 0)

		for c in range(a, limit + 1):
		ee = e
		while ee > 0 and arr_e[ee] != c:
		ee = next[ee - 1]

		if arr_e[ee] == c:
		ee += 1

		ans += f(i + 1, False, reach and c == limit, ee)

		return ans % int(1e9 + 7)

		return f(0, True, True, 0)

		return (good(s2) - good(s1) + int(evil not in s1)) % int(1e9 + 7)