leetcode1977
class Solution:
class Solution:
def __init__(self):
def __init__(self):
self.mod = 10 ** 9 + 7
self.mod = 10 ** 9 + 7
def numberOfCombinations(self, num: str) -> int:
def numberOfCombinations(self, num: str) -> int:
n = len(num)
n = len(num)
lcs = [[0] * (n+1) for _ in range(n+1)]
lcs = [[0] * (n+1) for _ in range(n+1)]
preSum = [[0] * (n+1) for _ in range(n+1)]
preSum = [[0] * (n+1) for _ in range(n+1)]
for i in range(n-2, -1, -1):
for i in range(n-2, -1, -1):
for j in range(i+1, n):
for j in range(i+1, n):
if num[i] == num[j]:
if num[i] == num[j]:
lcs[i][j] = 1 + lcs[i+1][j+1]
lcs[i][j] = 1 + lcs[i+1][j+1]
else:
else:
lcs[i][j] = 0
lcs[i][j] = 0
for i in range(n):
for i in range(n):
for l in range(1, i+2):
for l in range(1, i+2):
j = i - l + 1
j = i - l + 1
# cur = 0
if num[j] == '0':
if num[j] == '0':
cur = 0
cur = 0
elif j == 0:
elif j == 0:
cur = 1
cur = 1
else:
else:
# maxL2 = 0
if j < l:
if j < l:
maxL2 = j
maxL2 = j
else:
else:
cl = lcs[j-l][j]
cl = lcs[j-l][j]
if cl >= l or num[j-l+cl] < num[j+cl]:
if cl >= l or num[j-l+cl] < num[j+cl]:
maxL2 = l
maxL2 = l
else:
else:
maxL2 = l - 1
maxL2 = l - 1
cur = preSum[j-1][maxL2]
cur = preSum[j-1][maxL2]
preSum[i][l] = preSum[i][l-1] + cur
preSum[i][l] = preSum[i][l-1] + cur
return preSum[n-1][n] % self.mod
return preSum[n-1][n] % self.mod