[LeetCode] 每日一题 2999. 统计强大整数的数目（记忆化搜索 + 复杂条件）

题目描述

给你三个整数 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 的后缀。

题目链接

https://leetcode.cn/problems/count-the-number-of-powerful-integers

示例输入

示例 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 。

解题思路

这道题比平时的每日一题明显复杂不少，条件判断非常细致繁琐。我一开始确实也尝试了 DFS 来暴力枚举所有满足条件的数值，但在逐位判断的过程中，发现搜索空间太大，导致直接 TLE（超时）⏳

后来参考了题解，意识到这其实是一个典型的数位 DP + 记忆化搜索问题，类似于构造满足上下界的数字，并附加了一个后缀限制的条件。

思路拆解如下：

我们用一个函数 dfs(i, limitMin, limitHigh) 表示当前构造到第 i 位，是否仍然受 start 和 finish 限制。

• limitMin：当前数位是否还受 start 的限制。如果之前的位都是和 start 相等的，就说明仍受限制；

• limitMax：同理，表示是否受 finish 的限制；

• 当 index < max.length - s.length 的时候，我们可以填 [b, min(b, limit)] 范围内的任意数；

• 一旦到了后缀部分，我们必须强制填入 s 中对应位置的字符（后缀匹配）；

• 注意在不受限制时使用记忆化数组来加速搜索，避免重复递归。

此外还需要对 start 和 finish 补零到同样长度，以便进行统一的运算。

代码实现

class Solution {
    public long numberOfPowerfulInt(long start, long finish, int limit, String s) {
        String min = String.valueOf(start);
        String max = String.valueOf(finish);
        int n = max.length();
        min = "0".repeat(n - min.length()) + min;
        long[] memory = new long[n];
        Arrays.fill(memory, -1);
        return dfs(0, true, true, min.toCharArray(), max.toCharArray(), s.toCharArray(), limit, memory);
    }

    private static long dfs(int index, boolean limitMin, boolean limitMax, char[] min, char[] max, char[] s, int limit,
            long[] memory) {
        if (index == max.length) {
            return 1;
        }
        if (!limitMin && !limitMax && memory[index] != -1) {
            return memory[index];
        }
        //[a, b]
        int a = 0, b = 9;
        if (limitMin) {
            a = min[index] - '0';
        }
        if (limitMax) {
            b = max[index] - '0';
        }
        long res = 0;
        if (index < max.length - s.length) {
            for (int i = a; i <= Math.min(limit, b); i++) {
                res += dfs(index + 1, limitMin && i == a, limitMax && i == b, min, max, s, limit, memory);
            }
        } else {
            int x = s[index - (max.length - s.length)] - '0';
            if (a <= x && x <= b) {
                res = dfs(index + 1, limitMin && x == a, limitMax && x == b, min, max, s, limit, memory);
            }
        }
        if (!limitMax && !limitMin) {
            memory[index] = res;
        }
        return res;
    }
}

复杂度分析

• 时间复杂度： O(n × limit)，其中 n 是最大数字的位数，limit 是每位能取的最大数字上限，通过记忆化避免了重复搜索 🌟

• 空间复杂度： O(n)，主要用于记忆化数组 memory 的存储 🧠

总结

这道题让我真正体会到数位 DP的强大，也让我意识到在面对大量组合时，直接 DFS 很容易超时，这时候就必须考虑剪枝和记忆化的策略。题目的条件特别细致，像是“后缀匹配”“数位限制”“上下边界”，这些条件都不能遗漏。

在实现过程中，对每一位都要非常小心处理约束条件，稍有差错就会导致漏解或错解。这种题确实锻炼细节思维与代码功底，也让我回顾了一些早期没掌握好的数位动态规划技巧 🔍

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。