Count stepping numbers in range

String Dynamic Programming

27.8% acceptance

Feb 25, 2026

356

Given two positive integers low and high represented as strings, find the count of stepping numbers in the inclusive range [low, high]. A stepping number is an integer such that all of its adjacent digits have an absolute difference of exactly 1. Return an integer denoting the count of stepping numbers in the inclusive range [low, high]. Since the answer may be very large, return it modulo 109 + 7. Note: A stepping number should not have a leading zero.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn count_stepping_numbers(low: String, high: String) -> i32 {
    const MOD: i64 = 1_000_000_007;
    const MAX_LEN: usize = 101;

    fn build_free_table() -> Vec<Vec<i64>> {
      let mut ft = vec![vec![0i64; MAX_LEN + 1]; 10];
      for d in 0..10usize { ft[d][0] = 1; }
      for r in 1..=MAX_LEN {
        for d in 0..10usize {
          if d > 0 { ft[d][r] = (ft[d][r] + ft[d-1][r-1]) % MOD; }
          if d < 9 { ft[d][r] = (ft[d][r] + ft[d+1][r-1]) % MOD; }
        }
      }
      ft
    }

    fn count_k_digits(k: usize, ft: &[Vec<i64>]) -> i64 {
      if k == 0 { return 0; }
      let mut total = 0i64;
      for d in 1..=9usize { total = (total + ft[d][k-1]) % MOD; }
      total
    }

    fn is_stepping(s: &[u8]) -> bool {
      s.windows(2).all(|w| ((w[0] as i32) - (w[1] as i32)).abs() == 1)
    }

    fn count_upto(s: &[u8], ft: &[Vec<i64>]) -> i64 {
      let n = s.len();
      let mut result = 0i64;
      for l in 1..n { result = (result + count_k_digits(l, ft)) % MOD; }
      let mut prev: i32 = -1;
      for pos in 0..n {
        let limit = (s[pos] - b'0') as usize;
        let start = if pos == 0 { 1usize } else { 0usize };
        for d in start..limit {
          if prev >= 0 && ((d as i32) - prev).abs() != 1 { continue; }
          result = (result + ft[d][n - pos - 1]) % MOD;
        }
        if prev >= 0 && ((limit as i32) - prev).abs() != 1 { return result; }
        if pos == 0 && limit == 0 { return result; }
        prev = limit as i32;
      }
      result = (result + 1) % MOD;
      result
    }

    let ft = build_free_table();
    let low_bytes = low.as_bytes();
    let high_bytes = high.as_bytes();
    let count_high = count_upto(high_bytes, &ft);
    let count_low = count_upto(low_bytes, &ft);
    let low_valid = if is_stepping(low_bytes) && low_bytes[0] != b'0' { 1i64 } else { 0i64 };
    ((count_high - count_low + low_valid + MOD) % MOD) as i32
  }
}