1151. Stepping Numbers

• Difficulty: Medium

• Topics: Backtracking

• Similar Questions:

Problem:

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

Solutions:

class Solution {
public:
    vector<int> countSteppingNumbers(int low, int high) {
        vector<int> ret;
        if (low <= 0 && high >= 0)  ret.push_back(0);
        for (int i = 1; i <= 9; ++i) {
            dfs(i, low, high, ret);
        }

        sort(ret.begin(), ret.end());

        return ret;
    }


private:
    void dfs(int num, int low, int high, vector<int>& ret) {
        if (num > high) return;
        if (num >= low) {
            ret.push_back(num);
        }

        int lastDigit = num % 10;
        if (lastDigit - 1 >= 0 && num < INT_MAX / 10) {
            dfs(num * 10 + (lastDigit - 1), low, high, ret);
        }

        if (lastDigit + 1 <= 9 && num < INT_MAX / 10) {
            dfs(num * 10 + (lastDigit + 1), low, high, ret);
        }
    }

};