count-stepping-numbers-in-range

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given two positive integers <code>low</code> and <code>high</code> represented as strings, find the count of stepping numbers in the inclusive range <code>[low, high]</code>.

A stepping number is an integer such that all of its adjacent digits have an absolute difference of exactly <code>1</code>.

Return an integer denoting the count of stepping numbers in the inclusive range <code>[low, high]</code>. 

Since the answer may be very large, return it modulo <code>109 + 7</code>.

Note: A stepping number should not have a leading zero.

&nbsp;
Example 1:

<pre>
Input: low = &quot;1&quot;, high = &quot;11&quot;
Output: 10
Explanation: The stepping numbers in the range [1,11] are 1, 2, 3, 4, 5, 6, 7, 8, 9 and 10. There are a total of 10 stepping numbers in the range. Hence, the output is 10.</pre>

Example 2:

<pre>
Input: low = &quot;90&quot;, high = &quot;101&quot;
Output: 2
Explanation: The stepping numbers in the range [90,101] are 98 and 101. There are a total of 2 stepping numbers in the range. Hence, the output is 2. </pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= int(low) &lt;= int(high) &lt; 10100</code></li>
	<li><code>1 &lt;= low.length, high.length &lt;= 100</code></li>
	<li><code>low</code> and <code>high</code> consist of only digits.</li>
	<li><code>low</code> and <code>high</code> don&#39;t have any leading zeros.</li>
</ul>

countSteppingNumbers

Count Stepping Numbers in Range

Stepping Numbers

stepping-numbers

步进数

String

Dynamic Programming

给你两个正整数&nbsp;<code>low</code> 和&nbsp;<code>high</code>&nbsp;，都用字符串表示，请你统计闭区间 <code>[low, high]</code>&nbsp;内的 步进数字&nbsp;数目。

如果一个整数相邻数位之间差的绝对值都 恰好&nbsp;是 <code>1</code>&nbsp;，那么这个数字被称为 步进数字&nbsp;。

请你返回一个整数，表示闭区间&nbsp;<code>[low, high]</code>&nbsp;之间步进数字的数目。

由于答案可能很大，请你将它对&nbsp;<code>109 + 7</code>&nbsp;取余&nbsp;后返回。

注意：步进数字不能有前导 0 。

&nbsp;

示例 1：

<pre>输入：low = "1", high = "11"
输出：10
解释：区间 [1,11] 内的步进数字为 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 和 10 。总共有 10 个步进数字。所以输出为 10 。</pre>

示例 2：

<pre>输入：low = "90", high = "101"
输出：2
解释：区间 [90,101] 内的步进数字为 98 和 101 。总共有 2 个步进数字。所以输出为 2 。</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= int(low) &lt;= int(high) &lt; 10100</code></li>
	<li><code>1 &lt;= low.length, high.length &lt;= 100</code></li>
	<li><code>low</code> 和&nbsp;<code>high</code>&nbsp;只包含数字。</li>
	<li><code>low</code> 和&nbsp;<code>high</code>&nbsp;都不含前导 0 。</li>
</ul>