统计范围内的步进数字数目

难度: Hard

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

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

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

由于答案可能很大，请你将它对 10⁹ + 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) < 10¹⁰⁰
1 <= low.length, high.length <= 100
low 和 high 只包含数字。
low 和 high 都不含前导 0 。

Submission

运行时间: 57 ms

内存: 16.3 MB

MOD = 1_000_000_007
adjoin = [[1], [0, 2], [1, 3], [2, 4], [3, 5], [4, 6], [5, 7], [6, 8], [7, 9], [8]]
MAXLENGTH = 102
result = [[0] * MAXLENGTH for _ in range(10)]
resultMix = [[0] * MAXLENGTH for _ in range(10)]
resultLowerSum = [[0] * MAXLENGTH for _ in range(10)]
temp, tempSum = list(range(10)), 10
for i in range(10):
    result[i][1] = 1
    resultMix[i][1] = 1
    resultLowerSum[i][1] = i
for j in range(2, MAXLENGTH):
    for i in range(10):
        res = 0
        for k in adjoin[i]:
            res += result[k][j - 1]
        result[i][j] = res % MOD
        if i > 0:
            resultMix[i][j] = (resultMix[i][j - 1] + result[i][j]) % MOD
            resultLowerSum[i][j] = tempSum
            tempSum = (tempSum + result[i][j]) % MOD


class Solution:
    def countSteppingNumbers(self, low: str, high: str) -> int:
        def count(li: List[int]) -> int:
            length = len(li)
            res = resultLowerSum[li[0]][length]
            if length == 1:
                return res + 1
            pre = li[0]
            for idx, curNum in enumerate(li[1:], 1):
                if curNum < adjoin[pre][0]:
                    break
                if curNum == adjoin[pre][0]:
                    if idx == length - 1:
                        res += 1
                    pre = adjoin[pre][0]
                    continue
                res += result[adjoin[pre][0]][length - idx]
                if len(adjoin[pre]) == 1:
                    break
                if adjoin[pre][-1] > curNum:
                    break
                if curNum == adjoin[pre][-1]:
                    if idx == length - 1:
                        res += 1
                    pre = adjoin[pre][-1]
                    continue
                res += result[adjoin[pre][-1]][length - idx]
                break
            return res
            
            

        def check(li: List[int]) -> int:
            for idx, curNum in enumerate(li[1:], 1):
                if abs(curNum - li[idx - 1]) == 1:
                    continue
                else:
                    return 0
            return 1

        highList = [int(i) for i in high]
        highResult = count(highList)

        lowList = [int(i) for i in low]
        lowResult = count(lowList)
        return (highResult - lowResult + check(lowList)) % MOD

Explain

题解采用动态规划的思想，结合记忆化搜索的方法来统计步进数字。首先，定义一个多维数组result，其中result[i][j]表示长度为j且以数字i开始的步进数字数量。通过一个预处理步骤，使用动态规划填充这个数组。动态转移方程基于前一位的数字和其相邻数字构建，确保每次构建的数字符合步进数字的要求。在主函数中，使用两个辅助函数来计算范围[low, high]内的步进数字，分别计算小于或等于high的步进数字和小于low的步进数字，然后求差值并校验low是否为步进数字，以得到最终答案。

时间复杂度: O(n)

空间复杂度: O(1)

MOD = 1_000_000_007
adjoin = [[1], [0, 2], [1, 3], [2, 4], [3, 5], [4, 6], [5, 7], [6, 8], [7, 9], [8]]
MAXLENGTH = 102
result = [[0] * MAXLENGTH for _ in range(10)]
resultMix = [[0] * MAXLENGTH for _ in range(10)]
resultLowerSum = [[0] * MAXLENGTH for _ in range(10)]
temp, tempSum = list(range(10)), 10
for i in range(10):
    result[i][1] = 1
    resultMix[i][1] = 1
    resultLowerSum[i][1] = i
for j in range(2, MAXLENGTH):
    for i in range(10):
        res = 0
        for k in adjoin[i]:
            res += result[k][j - 1]
        result[i][j] = res % MOD
        if i > 0:
            resultMix[i][j] = (resultMix[i][j - 1] + result[i][j]) % MOD
            resultLowerSum[i][j] = tempSum
            tempSum = (tempSum + result[i][j]) % MOD

class Solution:
    def countSteppingNumbers(self, low: str, high: str) -> int:
        def count(li: List[int]) -> int:
            length = len(li)
            res = resultLowerSum[li[0]][length]
            if length == 1:
                return res + 1
            pre = li[0]
            for idx, curNum in enumerate(li[1:], 1):
                if curNum < adjoin[pre][0]:
                    break
                if curNum == adjoin[pre][0]:
                    if idx == length - 1:
                        res += 1
                    pre = adjoin[pre][0]
                    continue
                res += result[adjoin[pre][0]][length - idx]
                if len(adjoin[pre]) == 1:
                    break
                if adjoin[pre][-1] > curNum:
                    break
                if curNum == adjoin[pre][-1]:
                    if idx == length - 1:
                        res += 1
                    pre = adjoin[pre][-1]
                    continue
                res += result[adjoin[pre][-1]][length - idx]
                break
            return res
            
        

        def check(li: List[int]) -> int:
            for idx, curNum in enumerate(li[1:], 1):
                if abs(curNum - li[idx - 1]) == 1:
                    continue
                else:
                    return 0
            return 1

        highList = [int(i) for i in high]
        highResult = count(highList)

        lowList = [int(i) for i in low]
        lowResult = count(lowList)
        return (highResult - lowResult + check(lowList)) % MOD

Explore

在题解中，`result[i][j]`数组的定义是长度为`j`且以数字`i`开头的步进数字的数量。步进数字指的是数字中任意相邻两位的差的绝对值为1的数字。对`result`数组的填充采用动态规划方法，基于以下思想：若要构建一个长度为`j`且以`i`开头的步进数字，可以先考虑以`i`的相邻数字（即`i-1`或`i+1`，但需在0-9的范围内）开头的长度为`j-1`的步进数字，然后在其前面添加`i`。这样，`result[i][j]`可以通过累加`i`的所有合法相邻数字对应的`result[相邻数字][j-1]`来计算得出。通过预先计算并填充这个数组，我们可以快速回答任何关于特定长度和特定起始数字的步进数字数量的查询。

在题解中，算法设计只考虑数字的相邻数位间差为1，这是因为定义中步进数字特指其相邻数位的差的绝对值为1。如果考虑更广泛的数字差，那么将不再符合步进数字的定义，而成为一个不同的问题。仅考虑差为1的设计简化了问题模型和动态规划的状态转移，使得问题可以在可控的复杂度内解决，同时保持了算法的精度和效率，确保只计算符合步进数字定义的数。如果扩展到更广的数字差，可能会大大增加状态空间和计算的复杂性，而且不再满足原题设定。

题解中的预处理方法是针对不同长度和起始数字的步进数字进行计数，这种预处理方式在面对非常大或非常小的输入范围时依然有效。因为该预处理方法已经涵盖了从1位数到最大位数`MAXLENGTH`（在题解中设定为102）的所有可能长度的步进数字数量，无论输入范围有多大或多小，预处理数组可以提供快速的查询结果。此外，处理大数字范围时，动态规划的效率优势尤为明显，因为直接计算大范围内步进数字的数量可能非常耗时，而通过预处理和快速查询结果数组，可以显著减少计算时间。