Giả sử, chúng ta có một chuỗi 'i' bao gồm các chữ cái viết thường và một số nguyên khác 'j'. Chúng ta phải tìm xem có bao nhiêu chuỗi có kích thước bằng kích thước của 'i' và nhỏ hơn hoặc bằng 'i' về mặt từ vựng và không có ký tự nào bằng nhau liên tiếp lớn hơn 'j'.
Câu trả lời phải được tính bằng cách tìm Mod, kết quả là 10 ^ 9 + 7.
Vì vậy, nếu đầu vào là i ="app", j =2, thì đầu ra sẽ là 405.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
nếu j <=0, thì
-
trả về 0
-
-
m:=10 ^ 9 + 7
-
n:=kích thước của tôi
-
nums:=một danh sách mới chứa (biểu diễn unicode của ký tự - biểu diễn unicode của "a") cho mỗi ký tự có trong s
-
return dp (0, True, -1, 0) mod m
-
Định nghĩa một hàm dp (). Điều này sẽ có vị trí, ràng buộc, cuối cùng, đếm
-
nếu count> j khác 0 thì
-
trả về 0
-
-
nếu pos giống với n thì
-
trả lại 1
-
-
num:=nums [pos]
-
res:=0
-
đối với tôi trong phạm vi 0 đến (num + 1 nếu bị ràng buộc, nếu không là 26), hãy thực hiện
-
res:=res + dp (pos + 1, true nếu bị ràng buộc và tôi giống với num, i, count * (true nếu tôi giống với last) + 1)
-
-
trả lại res
-
-
Từ phương thức chính trả về dp (0, True, -1, 0)% m
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
class Solution:
def solve(self, s, k):
if k <= 0:
return 0
MOD = 10 ** 9 + 7
n = len(s)
nums = [ord(char) - ord("a") for char in s]
def dp(pos, bound, last, count):
if count > k:
return 0
if pos == n:
return 1
num = nums[pos]
res = 0
for i in range(num + 1 if bound else 26):
res += dp(pos + 1, bound and i == num, i, count * (i == last) + 1)
return res
return dp(0, True, -1, 0) % MOD
ob = Solution()
print(ob.solve('app',2)) Đầu vào
i = "app" j = 2
Đầu ra
405