Count Stepping Numbers in Range

• Initialize a queue and add all single-digit numbers (1 to 9) to it.
• Initialize a counter count to 0.
• Convert low and high strings to a type that supports large numbers, like BigInteger in Java, for easy comparison.
• While the queue is not empty:
  • Dequeue a number currentNum.
  • If currentNum is greater than high, we can prune this path as all subsequent numbers generated from it will also be greater.
  • If currentNum is within the range [low, high], increment count.
  • Get the last digit of currentNum: lastDigit = currentNum % 10.
  • If lastDigit > 0, form nextNum1 = currentNum * 10 + (lastDigit - 1). If nextNum1 <= high, enqueue it.
  • If lastDigit < 9, form nextNum2 = currentNum * 10 + (lastDigit + 1). If nextNum2 <= high, enqueue it.
• Return count.

The core idea is to build stepping numbers digit by digit. We can start with all single-digit numbers (1-9) as the initial set of stepping numbers.

We use a queue for the BFS process. Initially, the queue contains all single-digit numbers. In each step of the BFS, we dequeue a number u. If u is within the given range [low, high], we count it.

Then, we generate new stepping numbers by appending a digit to u. Let the last digit of u be last_d. The new digit can be last_d - 1 or last_d + 1, provided it's a valid digit (0-9). For example, if u is 21, last_d is 1. We can append 0 or 2. The new numbers are 210 and 212.

These newly generated numbers are enqueued for further processing, but only if they do not exceed the high bound. Since the numbers can be very large (up to 100 digits), we should use a data type that can handle them, such as BigInteger in Java. The process continues until the queue is empty or all remaining numbers in the queue are greater than high.

1import java.math.BigInteger;2import java.util.LinkedList;3import java.util.Queue;4 5class Solution {6    public int countSteppingNumbers(String low, String high) {7        BigInteger lowNum = new BigInteger(low);8        BigInteger highNum = new BigInteger(high);9        int count = 0;10        final int MOD = 1_000_000_007;11 12        Queue<BigInteger> q = new LinkedList<>();13        for (long i = 1; i <= 9; i++) {14            q.add(BigInteger.valueOf(i));15        }16 17        while (!q.isEmpty()) {18            BigInteger curr = q.poll();19 20            if (curr.compareTo(highNum) > 0) {21                continue;22            }23 24            if (curr.compareTo(lowNum) >= 0) {25                count = (count + 1) % MOD;26            }27 28            int lastDigit = curr.mod(BigInteger.TEN).intValue();29 30            if (lastDigit > 0) {31                BigInteger nextNum = curr.multiply(BigInteger.TEN).add(BigInteger.valueOf(lastDigit - 1));32                if (nextNum.compareTo(highNum) <= 0) {33                    q.add(nextNum);34                }35            }36 37            if (lastDigit < 9) {38                BigInteger nextNum = curr.multiply(BigInteger.TEN).add(BigInteger.valueOf(lastDigit + 1));39                if (nextNum.compareTo(highNum) <= 0) {40                    q.add(nextNum);41                }42            }43        }44        return count;45    }46}

• The final answer is calculated as (count(high) - count(low) + (isStepping(low) ? 1 : 0)) % MOD.
• Implement a function count(String s) which calculates the number of stepping numbers between 1 and s (inclusive).
• count(s) is implemented using a recursive helper function dfs with memoization. The result of count(s) is (dfs(s, ...) - 1 + MOD) % MOD. The -1 is to exclude the number 0, which our dfs implementation counts.
• The dfs(s, index, prevDigit, isTight, isLeadingZero) function is defined as follows:
  • Base Case: If index == s.length(), we have successfully formed a valid number. Return 1.
  • Memoization: Check if the state (index, prevDigit, isTight, isLeadingZero) has been computed. If so, return the stored value.
  • Transitions: Loop through possible digits for the current index. The upper limit for the digit is s.charAt(index) - '0' if isTight is true, otherwise it's 9.
  • For each digit:
    • If isLeadingZero is true:
      • If digit is 0, we continue with leading zeros: recurse with dfs(..., isLeadingZero=true).
      • If digit is non-zero, this is the first digit. Recurse with dfs(..., isLeadingZero=false).
    • If isLeadingZero is false:
      • Check if abs(digit - prevDigit) == 1. If it is, recurse with dfs(...).
  • Sum up the results from recursive calls (modulo MOD).
  • Store the result in the memoization table and return it.
• The initial call to the helper function is dfs(s, 0, 10, true, true), where prevDigit=10 is a sentinel value for the initial state.
• Implement a simple helper isStepping(String s) to check if low itself is a stepping number.

We design a recursive function, let's call it dfs, that counts valid numbers from a given state. The state needs to capture all information required to decide the next digits without violating any constraints. We use memoization to store the results of dfs for each state to avoid re-computation.

The state for our dfs function will be (index, prevDigit, isTight, isLeadingZero):

• index: The current digit position we are filling (from left, 0-indexed).
• prevDigit: The value of the previously placed digit. We can use a special value (e.g., 10) to indicate that no digit has been placed yet.
• isTight: A boolean flag. It's true if we are restricted to the digits of the upper bound string N. For example, if N = "854" and we have placed 85, the next digit can only be from 0 to 4. If we had placed 84, the next digit could be 0-9.
• isLeadingZero: A boolean flag to handle leading zeros. A number cannot start with a zero (unless it's the number 0 itself). This flag helps us enforce this rule.

The main logic is to calculate count(high) and count(low-1). A simpler way to get the count in [low, high] is (count(high) - count(low) + isLowSteppingNumber). The count(N) function will call dfs(N_str, 0, 10, true, true). This counts stepping numbers in [0, N]. Since the problem asks for positive integers, we subtract 1 to exclude 0.

1import java.util.Arrays;2 3class Solution {4    private static final int MOD = 1_000_000_007;5    private String s;6    private int[][][][] memo;7 8    private int dfs(int index, int prevDigit, boolean isTight, boolean isLeadingZero) {9        if (index == s.length()) {10            return 1; // A valid number is formed11        }12        if (memo[index][prevDigit][isTight ? 1 : 0][isLeadingZero ? 1 : 0] != -1) {13            return memo[index][prevDigit][isTight ? 1 : 0][isLeadingZero ? 1 : 0];14        }15 16        long ans = 0;17        int upperBound = isTight ? (s.charAt(index) - '0') : 9;18 19        for (int digit = 0; digit <= upperBound; digit++) {20            boolean newTight = isTight && (digit == upperBound);21            if (isLeadingZero) {22                if (digit == 0) {23                    ans = (ans + dfs(index + 1, 10, newTight, true)) % MOD;24                } else {25                    ans = (ans + dfs(index + 1, digit, newTight, false)) % MOD;26                }27            } else {28                if (Math.abs(digit - prevDigit) == 1) {29                    ans = (ans + dfs(index + 1, digit, newTight, false)) % MOD;30                }31            }32        }33 34        return memo[index][prevDigit][isTight ? 1 : 0][isLeadingZero ? 1 : 0] = (int) ans;35    }36 37    private int count(String numStr) {38        this.s = numStr;39        this.memo = new int[s.length()][11][2][2];40        for (int[][][] a : memo) {41            for (int[][] b : a) {42                for (int[] c : b) {43                    Arrays.fill(c, -1);44                }45            }46        }47        // dfs counts numbers in [0, s], including 0.48        // We want count in [1, s], so subtract 1 for 0.49        return (dfs(0, 10, true, true) - 1 + MOD) % MOD;50    }51 52    private boolean isStepping(String s) {53        for (int i = 0; i < s.length() - 1; i++) {54            if (Math.abs(s.charAt(i) - s.charAt(i + 1)) != 1) {55                return false;56            }57        }58        return true;59    }60 61    public int countSteppingNumbers(String low, String high) {62        int countHigh = count(high);63        int countLow = count(low);64        65        int ans = (countHigh - countLow + MOD) % MOD;66        if (isStepping(low)) {67            ans = (ans + 1) % MOD;68        }69        70        return ans;71    }72}