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

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

请你返回一个整数，表示闭区间 [low, high] 之间步进数字的数目。

由于答案可能很大，请你将它对 109 + 7 取余 后返回。

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

 

示例 1：

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

示例 2：

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

 

提示：

  • 1 <= int(low) <= int(high) < 10100
  • 1 <= low.length, high.length <= 100
  • low 和 high 只包含数字。
  • low 和 high 都不含前导 0 。

灵神

思路

定义表示不超过的步进数字数目。那么答案就是

由于是个很大的数字，不方便减一（Python 用户可以无视），所以用 表示：如果是步进数字，那么多减了 1，再加 1 补回来。

如何计算 呢？（下文用表示的字符串形式）

一种通用套路是，定义表示构造第 i 位及其之后数位的合法方案数，其余参数的含义为：

  • 表示上一个数位的值。如果 为 false，可以忽略 pre\textit{pre}pre。
  • isLimit\textit{isLimit}isLimit 表示当前是否受到了 nnn 的约束（注意要构造的数字不能超过 nnn）。若为真，则第 iii 位填入的数字至多为 s[i]s[i]s[i]，否则可以是 999。如果在受到约束的情况下填了 s[i]s[i]s[i]，那么后续填入的数字仍会受到 nnn 的约束。例如 n\=123n=123n\=123，那么 i\=0i=0i\=0 填的是 111 的话，i\=1i=1i\=1 的这一位至多填 222。
  • isNum\textit{isNum}isNum 表示 iii 前面的数位是否填了数字。若为假，则当前位可以跳过（不填数字），或者要填入的数字至少为 111；若为真，则要填入的数字可以从 000 开始。例如 n\=123n=123n\=123，在 i\=0i=0i\=0 时跳过的话，相当于后面要构造的是一个 999999 以内的数字了，如果 i\=1i=1i\=1 不跳过，那么相当于构造一个 101010 到 999999 的两位数，如果 i\=1i=1i\=1 也跳过，相当于构造的是一个 999 以内的数字。

实现细节

递归入口：f(0, 0, true, false)，表示：

  • 从 s[0]s[0]s[0] 开始枚举；
  • pre\textit{pre}pre 初始化成什么都可以，因为填第一个数的时候是忽略 pre\textit{pre}pre 的。
  • 一开始要受到 nnn 的约束（否则就可以随意填了，这肯定不行）；
  • 一开始没有填数字。

递归中：

  • 如果 isNum\textit{isNum}isNum 为假，说明前面没有填数字，那么当前也可以不填数字。一旦从这里递归下去，isLimit\textit{isLimit}isLimit 就可以置为 false 了，这是因为 s[0]s[0]s[0] 必然是大于 000 的，后面就不受到 nnn 的约束了。或者说，最高位不填数字，后面无论怎么填都比 nnn 小。
  • 如果 isNum\textit{isNum}isNum 为真，那么当前必须填一个数字。枚举填入的数字，根据 isNum\textit{isNum}isNum 和 isLimit\textit{isLimit}isLimit 来决定填入数字的范围。

递归终点：当 iii 等于 sss 长度时，如果 isNum\textit{isNum}isNum 为真，则表示得到了一个合法数字（因为不合法的不会继续递归下去），返回 111，否则返回 000。

关于取模的细节，见文末的讲解。

答疑

问：记忆化四个状态有点麻烦，能不能只记忆化 iii 和 pre\textit{pre}pre 这两个状态？

答：可以的！比如 n\=234n=234n\=234，第一位填 222，第二位填 333，后面无论怎么递归，都不会再次递归到第一位填 222，第二位填 333 的情况，所以不需要记录。又比如，第一位不填，第二位也不填，后面无论怎么递归也不会再次递归到这种情况，所以也不需要记录。

根据这个例子，我们可以只记录不受到约束时的状态 (i,mask,false,true)(i,\textit{mask},\text{false},\text{true})(i,mask,false,true)。比如 n\=456n=456n\=456，第一位（最高位）填的 333，那么继续递归，后面就可以随便填，所以状态 (1,3,false,true)(1,3,\text{false},\text{true})(1,3,false,true) 就表示 i\=0i=0i\=0 填 333，从 i\=1i=1i\=1 往后随便填的方案数。

由于后面两个参数恒为 false\text{false}false 和 true\text{true}true，所以可以不用记忆化，只记忆化 iii 和 pre\textit{pre}pre。

注：Python 有 @cache，可以无视上面说的。

问：能不能只记忆化 iii？

答：这是不行的。想一想，我们为什么要用记忆化？如果递归到同一个状态时，计算出的结果是一样的，那么第二次递归到同一个状态，就可以直接返回第一次计算的结果了。通过保存第一次计算的结果，来优化时间复杂度。

由于前面选的数字会影响后面选的数字，两次递归到相同的 iii，如果前面选的数字不一样，计算出的结果就可能是不一样的。如果只记忆化 iii，就可能会算出错误的结果。

也可以这样理解：记忆化搜索要求递归函数无副作用（除了修改 memo 数组），从而保证递归到同一个状态时，计算出的结果是一样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def countSteppingNumbers(self, low: str, high: str) -> int:
        MOD = 10 ** 9 + 7
        def calc(s: str) -> int:
            @cache  # 记忆化搜索
            def f(i: int, pre: int, is_limit: bool, is_num: bool) -> int:
                if i == len(s):
                    return int(is_num)  # is_num 为 True 表示得到了一个合法数字
                res = 0
                if not is_num:  # 可以跳过当前数位
                    res = f(i + 1, pre, False, False)
                low = 0 if is_num else 1  # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）
                up = int(s[i]) if is_limit else 9  # 如果前面填的数字都和 n 的一样，那么这一位至多填 s[i]（否则就超过 s 啦）
                for d in range(low, up + 1):  # 枚举要填入的数字 d
                    if not is_num or abs(d - pre) == 1:  # 第一位数字随便填，其余必须相差 1
                        res += f(i + 1, d, is_limit and d == up, True)
                return res % MOD
            return f(0, 0, True, False)
        return (calc(high) - calc(str(int(low) - 1))) % MOD