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 · 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