Ladder Numbers in a Range

Hard

Call a positive integer a **ladder number** if every two neighboring digits in it differ by exactly 1. For instance, 4565 and 10 are ladder numbers, while 122 and 135 are not. Every single-digit number counts as a ladder number too. The ends of the range are given as strings lo and hi, since they can be very long. Count the ladder numbers from lo to hi, both ends included. Numbers are written without leading zeros. The answer can be huge, so return it modulo 10⁹ + 7.

Example 1

lo="8", hi="23" → 6

The ladder numbers here are 8, 9, 10, 12, 21 and 23, six in total. 11 fails because its digits are equal, and 20 fails because 2 and 0 differ by 2.

Example 2

lo="300", hi="345" → 4

Within the range, only 321, 323, 343 and 345 are ladder numbers.

Example 3

lo="1", hi="9" → 9

Constraints

1 ≤ len(lo), len(hi) ≤ 100
lo and hi contain only digits and do not start with zero
1 ≤ int(lo) ≤ int(hi)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Dynamic Programming

Similar problems

Pattern With Dot and Star Hard Longest Balanced Bracket Stretch Hard Does the Text Fit the Pattern Hard Shuffle by Cutting and Swapping Hard Ways to Cross Out Hard

Input

lo="8", hi="23"

Expected

Run checks the first 3 tests in your browser. Submit checks all 103 tests on the server, hidden ones included.