#1977

Number of Ways to Separate Numbers

international master · 2170 · lc hard +32 · verified · 21.7% accepted · 536 likes · top 2%

⚑ String Matching DP (LCS / Edit Distance)

Description

You concatenated a list of positive integers into the string num without any commas. The original list was in non-decreasing order and no number had a leading zero.

Return the number of valid ways to parse num back into such a list of integers, modulo 10⁹ + 7.

Example 1:

Input: num = "327"

Output: 2

Explanation: You could have written down the numbers:

3, 27

327

Example 2:

Input: num = "094"

Output: 0

Explanation: No numbers can have leading zeros and all numbers must be positive.

Example 3:

Input: num = "0"

Output: 0

Explanation: No numbers can have leading zeros and all numbers must be positive.

Code

1

2

3

class Solution:
    def numberOfCombinations(self, num: str) -> int:

class Solution:
    def numberOfCombinations(self, num: str) -> int: