Stepping Numbers

01 · Question

A stepping number is an integer such that all of its adjacent digits have an absolute difference of exactly 1.

For example, 321 is a stepping number while 421 is not.

Given two integers low and high, return a sorted list of all the stepping numbers in the inclusive range [low, high].

02 · Analysis

Start from nonzero leading digits and extend x only with last_digit-1 or last_digit+1 when in 0..9. Each constructed number has one unique parent obtained by removing its last digit, so no duplicates arise. Stop beyond high and include 0 separately if the interval contains it. For M generated numbers and R outputs, time is O(M + R log(R+1)) including output sorting; recursion depth is the number of digits, and output uses O(R) space.

03 · Solution

Reference solution

1class Solution:
2    def countSteppingNumbers(self, low: int, high: int) -> List[int]:
3        res = set()
4
5        def dfs(num):
6            if num >= low and num <= high:
7                res.add(num)
8            if num == 0 or num > high:
9                return
10
11            last_digit = num % 10
12
13            if last_digit > 0:
14                dfs(num * 10 + last_digit - 1)
15            if last_digit < 9:
16                dfs(num * 10 + last_digit + 1)
17
18        for i in range(10):
19            dfs(i)
20
21        return sorted(list(res))

Synonymous Sentences

Letter Combinations of a Phone Number