目标
给你三个整数 start ，finish 和 limit 。同时给你一个下标从 0 开始的字符串 s ，表示一个 正 整数。
如果一个 正 整数 x 末尾部分是 s （换句话说，s 是 x 的 后缀），且 x 中的每个数位至多是 limit ，那么我们称 x 是 强大的 。
请你返回区间 [start..finish] 内强大整数的 总数目 。
如果一个字符串 x 是 y 中某个下标开始（包括 0 ），到下标为 y.length - 1 结束的子字符串，那么我们称 x 是 y 的一个后缀。比方说，25 是 5125 的一个后缀，但不是 512 的后缀。
示例 1：
输入：start = 1, finish = 6000, limit = 4, s = "124"
输出：5
解释：区间 [1..6000] 内的强大数字为 124 ，1124 ，2124 ，3124 和 4124 。这些整数的各个数位都 <= 4 且 "124" 是它们的后缀。注意 5124 不是强大整数，因为第一个数位 5 大于 4 。
这个区间内总共只有这 5 个强大整数。示例 2：
输入：start = 15, finish = 215, limit = 6, s = "10"
输出：2
解释：区间 [15..215] 内的强大整数为 110 和 210 。这些整数的各个数位都 <= 6 且 "10" 是它们的后缀。
这个区间总共只有这 2 个强大整数。示例 3：
输入：start = 1000, finish = 2000, limit = 4, s = "3000"
输出：0
解释：区间 [1000..2000] 内的整数都小于 3000 ，所以 "3000" 不可能是这个区间内任何整数的后缀。说明：
- 1 <= start <= finish <= 10^15
- 1 <= limit <= 9
- 1 <= s.length <= floor(log10(finish)) + 1
- s 数位中每个数字都小于等于 limit 。
- s 不包含任何前导 0 。
思路
返回指定区间 [start, finish] 内，后缀为 s 且每个数字不超过 limit 的数字个数。
数位dp，需要特殊处理后缀，比如 s = 10，start = 101, finish = 521 还剩两位时，01 < 10, 21 > 10 都不能计数。
代码
/**
* @date 2025-04-10 20:19
*/
public class NumberOfPowerfulInt2999 {
public long numberOfPowerfulInt(long start, long finish, int limit, String s) {
long suffix = Long.parseLong(s);
if (finish < suffix) {
return 0L;
}
int[] high = Long.toString(finish).chars().map(x -> x - '0').toArray();
int hl = high.length;
long[] mem = new long[hl];
int[] low = new int[hl--];
long tmp = start;
while (tmp > 0) {
low[hl--] = (int) (tmp % 10);
tmp /= 10;
}
Arrays.fill(mem, -1L);
return dfs(0, low, high, true, true, mem, limit, s);
}
public long dfs(int index, int[] low, int[] high, boolean isLowLimit, boolean isHighLimit, long[] mem, int limit, String s) {
if (index == high.length - s.length()) {
boolean unaviable = false;
if (isHighLimit) {
StringBuilder hr = new StringBuilder();
int tmp = index;
while (tmp < high.length) {
hr.append(high[tmp++]);
}
unaviable = Long.parseLong(hr.toString()) < Long.parseLong(s);
}
if (isLowLimit) {
StringBuilder lr = new StringBuilder();
while (index < high.length) {
lr.append(low[index++]);
}
unaviable = unaviable || Long.parseLong(lr.toString()) > Long.parseLong(s);
}
return unaviable ? 0 : 1;
}
if (!isLowLimit && !isHighLimit && mem[index] != -1) {
return mem[index];
}
long res = 0;
int up = isHighLimit ? Math.min(high[index], limit) : limit;
int down = isLowLimit ? low[index] : 0;
for (int i = down; i <= up; i++) {
res += dfs(index + 1, low, high, isLowLimit && i == low[index], isHighLimit && i == high[index], mem, limit, s);
}
if (!isHighLimit && !isLowLimit) {
mem[index] = res;
}
return res;
}
}
性能
