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].
Example 1:
Input: low = 0, high = 21
Output: [0,1,2,3,4,5,6,7,8,9,10,12,21]
Example 2:
Input: low = 10, high = 15
Output: [10,12]
Constraints:
0 <= low <= high <= 2 * 109
Solutions
Solution 1: BFS
First, if $low$ is $0$, we need to add $0$ to the answer.
Next, we create a queue $q$ and add $1 \sim 9$ to the queue. Then, we repeatedly take out elements from the queue. Let the current element be $v$. If $v$ is greater than $high$, we stop searching. If $v$ is in the range $[low, high]$, we add $v$ to the answer. Then, we need to record the last digit of $v$ as $x$. If $x \gt 0$, we add $v \times 10 + x - 1$ to the queue. If $x \lt 9$, we add $v \times 10 + x + 1$ to the queue. Repeat the above steps until the queue is empty.
The time complexity is $O(10 \times 2^{\log M})$, and the space complexity is $O(2^{\log M})$, where $M$ is the number of digits in $high$.