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, find and return a sorted list of all the Stepping Numbers in the range [low, high] inclusive.
Example 1:
Input: low = 0, high = 21
Output: [0,1,2,3,4,5,6,7,8,9,10,12,21]
Constraints:
0 <= low <= high <= 2 * 10^9
Solution:
class Solution {
public List<Integer> countSteppingNumbers(int low, int high) {
List<Integer> res = new ArrayList<>();
if (low > high) return res;
Queue<Long> queue = new LinkedList<>();
for (long i = 1; i <= 9; i++) queue.add(i);
if (low == 0) res.add(0);
while (!queue.isEmpty()) {
long p = queue.poll();
if (p < high) {
long last = p % 10;
if (last > 0) queue.add(p * 10 + last - 1);
if (last < 9) queue.add(p * 10 + last + 1);
}
if (p >= low && p <= high) {
res.add((int) p);
}
}
return res;
}
}