1215

1215. Stepping Numbers (Medium)

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

Companies: Epic Systems

Related Topics:
Backtracking, Breadth-First Search

Similar Questions:

• Count Stepping Numbers in Range (Hard)

Hints:

• Try to generate the numbers using recursion.
• In one step in the recursion, add a valid digit to the right of the current number.
• Save the number if it's in the range between low and high.

Solution 1. DFS

// OJ: https://leetcode.com/problems/stepping-numbers
// Author: github.com/lzl124631x
// Time: O(lg(R) * 2^lg(R))
// Space: O(lg(R))
class Solution {
public:
    vector<int> countSteppingNumbers(int low, int high) {
        vector<int> ans;
        if (low == 0) ans.push_back(0), ++low;
        int L = log(low) / log(10) + 1, R = log(high) / log(10) + 1;
        function<void(long, int, int)> dfs = [&](long n, int i, int len) {
            if (i == len) {
                if (n >= low && n <= high) ans.push_back(n);
                return;
            }
            int d = n % 10;
            if (d - 1 >= 0) dfs(n * 10 + d - 1, i + 1, len);
            if (d + 1 <= 9) dfs(n * 10 + d + 1, i + 1, len);
        };
        for (int len = L; len <= R; ++len) {
            for (int d = 1; d <= 9; ++d) dfs(d, 1, len);
        }
        return ans;
    }
};

Solution 2. BFS

// OJ: https://leetcode.com/problems/stepping-numbers
// Author: github.com/lzl124631x
// Time: O(lg(R) * 2^lg(R))
// Space: O(2^lg(R))
class Solution {
public:
    vector<int> countSteppingNumbers(int low, int high) {
        vector<int> ans;
        queue<long> q;
        for (int i = 1; i <= 9; ++i) q.push(i);
        if (low == 0) ans.push_back(0);
        while (q.size()) {
            long n = q.front(), d = n % 10;
            q.pop();
            if (n >= low && n <= high) ans.push_back(n);
            if (n < high) {
                if (d - 1 >= 0) q.push(n * 10 + d - 1);
                if (d + 1 <= 9) q.push(n * 10 + d + 1);
            }
        }
        return ans;
    }
};