Description
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 × 10 + x - 1 to the queue. If x \lt 9, we add v × 10 + x + 1 to the queue. Repeat the above steps until the queue is empty.
The time complexity is O(10 × 2log M), and the space complexity is O(2log M), where M is the number of digits in high.
PythonJavaC++GoTypeScript
class Solution:
def countSteppingNumbers(self, low: int, high: int) -> List[int]:
ans = []
if low == 0:
ans.append(0)
q = deque(range(1, 10))
while q:
v = q.popleft()
if v > high:
break
if v >= low:
ans.append(v)
x = v % 10
if x:
q.append(v * 10 + x - 1)
if x < 9:
q.append(v * 10 + x + 1)
return ans(code-box)
class Solution {
public List<Integer> countSteppingNumbers(int low, int high) {
List<Integer> ans = new ArrayList<>();
if (low == 0) {
ans.add(0);
}
Deque<Long> q = new ArrayDeque<>();
for (long i = 1; i < 10; ++i) {
q.offer(i);
}
while (!q.isEmpty()) {
long v = q.pollFirst();
if (v > high) {
break;
}
if (v >= low) {
ans.add((int) v);
}
int x = (int) v % 10;
if (x > 0) {
q.offer(v * 10 + x - 1);
}
if (x < 9) {
q.offer(v * 10 + x + 1);
}
}
return ans;
}
}(code-box)
class Solution {
public:
vector<int> countSteppingNumbers(int low, int high) {
vector<int> ans;
if (low == 0) {
ans.push_back(0);
}
queue<long long> q;
for (int i = 1; i < 10; ++i) {
q.push(i);
}
while (!q.empty()) {
long long v = q.front();
q.pop();
if (v > high) {
break;
}
if (v >= low) {
ans.push_back(v);
}
int x = v % 10;
if (x > 0) {
q.push(v * 10 + x - 1);
}
if (x < 9) {
q.push(v * 10 + x + 1);
}
}
return ans;
}
};(code-box)
func countSteppingNumbers(low int, high int) []int {
ans := []int{}
if low == 0 {
ans = append(ans, 0)
}
q := []int{1, 2, 3, 4, 5, 6, 7, 8, 9}
for len(q) > 0 {
v := q[0]
q = q[1:]
if v > high {
break
}
if v >= low {
ans = append(ans, v)
}
x := v % 10
if x > 0 {
q = append(q, v*10+x-1)
}
if x < 9 {
q = append(q, v*10+x+1)
}
}
return ans
}(code-box)
function countSteppingNumbers(low: number, high: number): number[] {
const ans: number[] = [];
if (low === 0) {
ans.push(0);
}
const q: number[] = [];
for (let i = 1; i < 10; ++i) {
q.push(i);
}
while (q.length) {
const v = q.shift()!;
if (v > high) {
break;
}
if (v >= low) {
ans.push(v);
}
const x = v % 10;
if (x > 0) {
q.push(v * 10 + x - 1);
}
if (x < 9) {
q.push(v * 10 + x + 1);
}
}
return ans;
}(code-box)
