在Python中,通过将数字字符串拆分来计算我们可以创建值列表的方法的程序
假设我们有一个字符串s。s包含从0-9的数字,我们还有另一个数字k。我们必须找出s可以表示为[1,k]中数字列表的不同方式的数量。如果答案非常大,则返回结果mod 10^9 + 7。
因此,如果输入像s =“3456”k = 500,则输出将为7,因为我们可以像[3,4,5,6],[34,5,6],[3,4,56],[3,45,6],[34,56],[345,6],[3,456]这样表示s。
要解决这个问题,我们将遵循以下步骤:
- m: = 10 ^ 9 + 7
-
N:s的大小
-
dp:一个大小为(N + 1)的列表,并填充为0
-
dp [N]:= 1
-
for i in range N – 1 to 0,递减1,
- curr_val:= 0
-
for j in range i to N,
- curr_val:= curr_val * 10 +(s [j]作为数字)
-
如果curr_val在1到k的范围内,
-
dp [i]:=(dp [i] + dp [j + 1])mod m
-
否则,
-
退出循环
- curr_val:= 0
-
返回dp [0]
以下是更好的理解实现的示例-
示例
class Solution:
def solve(self,s,k):
m = 10 ** 9 + 7
N = len(s)
dp = [0] *(N + 1)
dp [N] = 1
for i in range(N-1,-1,-1):
curr_val = 0
for j in range(i,N):
curr_val = curr_val * 10 + int(s [j])
if 1 <= curr_val <= k:
dp [i] =(dp [i] + dp [j + 1])%m
else:
break
返回dp [0]
ob = Solution()
s = “3456”
k = 500
print(ob.solve(s,k))
输入
"3456",500
输出
7