GeezerVison

The World Wide Web, restored to 800 pixels of glory.

GeezerVison is showing leetcodejavascript.com — #1215 - Stepping Numbers - LeetCode JavaScript Solutions

Back to all solutions

#1215 - Stepping Numbers

Medium • View on LeetCode • View on GitHub

Math Breadth-First Search Backtracking

Problem 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].

Solution

/**
 * @param {number} low
 * @param {number} high
 * @return {number[]}
 */
var countSteppingNumbers = function(low, high) {
  const result = [];

  if (low === 0) result.push(0);

  const minLength = low.toString().length;
  const maxLength = high.toString().length;

  for (let length = minLength; length <= maxLength; length++) {
    for (let start = 1; start <= 9; start++) {
      dfs(start.toString(), length);
    }
  }

  return result.sort((a, b) => a - b);

  function dfs(current, targetLength) {
    if (current.length === targetLength) {
      const num = parseInt(current);
      if (num >= low && num <= high) {
        result.push(num);
      }
      return;
    }

    const lastDigit = parseInt(current[current.length - 1]);

    if (lastDigit > 0) {
      dfs(current + (lastDigit - 1), targetLength);
    }
    if (lastDigit < 9) {
      dfs(current + (lastDigit + 1), targetLength);
    }
  }
};

You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.