Problem statement

https://binarysearch.com/problems/Decode-List-Message/

Solution

Equal to Leetcode 1416. Restore The Array.

Complexity

It is O(n * log(k)) for time and O(n) for space.

Code

class Solution:
    def solve(self, s, k):
        n = len(s)
        s = [int(i) for i in s] + [float("inf")]
        dp = [0] * n + [1]
        for i in range(n - 1, -1, -1):
            num, j = s[i], i + 1
            while 1 <= num <= k and j < n + 1:
                dp[i] = (dp[i] + dp[j]) % 1000000007
                num = 10 * num + s[j]
                j += 1
        return dp[0]