Hard

Count Stepping Numbers in Range

LAB

Return how many integers in [low, high] have adjacent digits differing by exactly one, modulo 1000000007.

EXAMPLES

Example 1

Input
{
  "low": "1",
  "high": "11"
}

Output
10

FUNCTION SHAPE

low: stringhigh: string→int

SOLUTION NOTE

Track previous digit to check stepping condition. Leading zeros don't count as real digits, so prev stays -1.

Reveal reference solution +

pythonREFERENCE

def countSteppingNumbers(self, low: str, high: str) -> int:
    MOD = 10**9 + 7

    def count(digits):
        @cache
        def dp(i, tight, leading_zero, prev):
            if i == len(digits): return 1
            max_d = int(digits[i]) if tight else 9
            res = 0
            for d in range(max_d + 1):
                next_tight = tight and d == max_d
                next_leading = leading_zero and d == 0
                if next_leading:
                    res = (res + dp(i+1, next_tight, True, -1)) % MOD
                elif prev == -1 or abs(d - prev) == 1:
                    res = (res + dp(i+1, next_tight, False, d)) % MOD
            return res
        return dp(0, True, True, -1)

    return (count(high) - count(str(int(low) - 1))) % MOD

TimeO(digits × 10)

SpaceO(digits × 10)

Open on LeetCode ↗