描述
给定两个正整数低和高代表字符串，在包含范围内找到步进数字的计数[低，高]。
阶梯号是一个整数，因此其所有相邻数字的绝对差为1。
返回一个整数，表示在包含范围内的步进数字[低，高]。
由于答案可能很大，因此将其返回modulo 10^9 + 7。
注意：阶梯号码不应具有领先的零。
示例1 ：
Input: low = "1", high = "11"
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.
示例2 ：
Input: low = "90", high = "101"
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.
约束：
1 <= int（low）<= int（高）<10^100
1 <= low.length，high.engength <= 100
low和high仅由数字组成。
low和high没有任何领先的零。
直觉
问题需要在给定范围内找到步进数字的计数[低，高]，其中阶梯数是一个整数，以使其所有相邻数字的绝对差异完全为1。要有效地计数这些踩踏数字，我们可以使用动态编程方法。
方法
Swift解决方案使用动态编程来解决问题。 REC函数递归根据某些条件来计算步进数字的计数。 DP阵列用于存储先前计算的结果，这有助于避免冗余计算并提高效率。
检查功能通过比较每对相邻数字之间的绝对差来检查一个数字是否是阶梯数字。
在countsteppingnumbers函数中，我们两次致电输入范围[Low，High]，然后从高数中减去计数。另外，如果低本身是阶梯数字，我们将结果添加1个。
代码（Swift）
该解决方案有效地处理大型输入，并按照问题语句的要求。
class Solution {
let mod = 1_000_000_007
var dp: [[[[Int]]]] = Array(
repeating: Array(
repeating: Array(repeating: Array(repeating: -1, count: 2), count: 10), count: 2),
count: 101)
func rec(_ s1: [Character], _ ind: Int, _ smaller: Bool, _ last: Int, _ start: Bool) -> Int {
if ind == s1.count {
return 1
}
if dp[ind][smaller ? 1 : 0][last][start ? 1 : 0] != -1 {
return dp[ind][smaller ? 1 : 0][last][start ? 1 : 0]
}
var ans = 0
if start || abs(last - 0) == 1 {
ans = (ans + rec(s1, ind + 1, smaller || (s1[ind] != "0"), 0, start)) % mod
}
if smaller {
for i in 1...9 {
if abs(last - i) == 1 || start {
ans = (ans + rec(s1, ind + 1, smaller, i, false)) % mod
}
}
} else {
let diff = Int(String(s1[ind]))!
if diff > 0 {
for i in 1..<diff {
if abs(last - i) == 1 || start {
ans = (ans + rec(s1, ind + 1, true, i, false)) % mod
}
}
}
if s1[ind] != "0" {
if abs(last - diff) == 1 || start {
ans = (ans + rec(s1, ind + 1, false, diff, false)) % mod
}
}
}
dp[ind][smaller ? 1 : 0][last][start ? 1 : 0] = ans
return ans
}
func check(_ s: String) -> Bool {
let sChars = Array(s)
for i in 0..<(sChars.count - 1) {
if abs(Int(String(sChars[i]))! - Int(String(sChars[i + 1]))!) != 1 {
return false
}
}
return true
}
func countSteppingNumbers(_ low: String, _ high: String) -> Int {
let x = rec(Array(high), 0, false, 0, true)
dp = Array(
repeating: Array(
repeating: Array(repeating: Array(repeating: -1, count: 2), count: 10), count: 2),
count: 101)
let y = rec(Array(low), 0, false, 0, true)
let z = check(low)
return (x - y + (z ? 1 : 0) + mod) % mod
}
}
来源：Github
联系人
我明确专注于上市时间，而没有优先考虑技术债务。我作为系统建筑师，移动（ios-swift，android-kotlin），前端（react-typescript）和后端（nodejs-.net-.net-php-php-php-php-kafka-sql）参加了系统架构师的预售/RFX活动。 -nosql）。我还通过知识转移到成功交付的知识转移，成立了预售作为CTO的工作。
ðLinkedIn：https://linkedin.com/in/sergeyleschev/
ðleetcode：https://leetcode.com/sergeyleschev/
ðTwitter：https://twitter.com/sergeyleschev
ðgithub：https://github.com/sergeyleschev
ð网站：https://sergeyleschev.github.io
ðreddit：https://reddit.com/user/sergeyleschev
ðQuora：https://quora.com/sergey-leschev
ð媒介：https://medium.com/@sergeyleschev
□PDF设计模式：Download