Tests failed w.r.t efficiency with Python


#1

Hi,

I submitted two variants of efficient solutions written in Python: a dictionary based and an array based. Both, however, are failed with the efficiency test while they are both efficient (considering, for example, the similar solutions in different programming languages).

This is my solution:
class Solution:
def solve(self, A, B):
N = A
S = B

    if S > 9*N:
        return 0

    d = [[0]*(9*i+1) for i in range(N+1)]

    d[1][0] = 0
    for j in range(1, 10):
        d[1][j] = 1

    i = 2
    while i <= N:
        for j in range(1, i*9+1):
            d[i][j] = 0
            for curr_digit in range(10):
                if 0 <= j-curr_digit < len(d[i-1]):
                    d[i][j] += (d[i-1][j-curr_digit] % 1000000007)
        i+=1

    if N < len(d) and S < len(d[N]):
        return d[N][S] % 1000000007
    else:
        return 0