题目描述
给你三个整数 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 <= 10151 <= limit <= 91 <= s.length <= floor(log10(finish)) + 1s 数位中每个数字都小于等于 limit 。s 不包含任何前导 0 。
解法
方法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | class Solution:
def numberOfPowerfulInt(self, start: int, finish: int, limit: int, s: str) -> int:
@cache
def dfs(pos: int, lim: int):
if len(t) < n:
return 0
if len(t) - pos == n:
return int(s <= t[pos:]) if lim else 1
up = min(int(t[pos]) if lim else 9, limit)
ans = 0
for i in range(up + 1):
ans += dfs(pos + 1, lim and i == int(t[pos]))
return ans
n = len(s)
t = str(start - 1)
a = dfs(0, True)
dfs.cache_clear()
t = str(finish)
b = dfs(0, True)
return b - a
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40 | class Solution {
private String s;
private String t;
private Long[] f;
private int limit;
public long numberOfPowerfulInt(long start, long finish, int limit, String s) {
this.s = s;
this.limit = limit;
t = String.valueOf(start - 1);
f = new Long[20];
long a = dfs(0, true);
t = String.valueOf(finish);
f = new Long[20];
long b = dfs(0, true);
return b - a;
}
private long dfs(int pos, boolean lim) {
if (t.length() < s.length()) {
return 0;
}
if (!lim && f[pos] != null) {
return f[pos];
}
if (t.length() - pos == s.length()) {
return lim ? (s.compareTo(t.substring(pos)) <= 0 ? 1 : 0) : 1;
}
int up = lim ? t.charAt(pos) - '0' : 9;
up = Math.min(up, limit);
long ans = 0;
for (int i = 0; i <= up; ++i) {
ans += dfs(pos + 1, lim && i == (t.charAt(pos) - '0'));
}
if (!lim) {
f[pos] = ans;
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 | class Solution {
public:
long long numberOfPowerfulInt(long long start, long long finish, int limit, string s) {
string t = to_string(start - 1);
long long f[20];
memset(f, -1, sizeof(f));
function<long long(int, bool)> dfs = [&](int pos, bool lim) -> long long {
if (t.size() < s.size()) {
return 0;
}
if (!lim && f[pos] != -1) {
return f[pos];
}
if (t.size() - pos == s.size()) {
return lim ? s <= t.substr(pos) : 1;
}
long long ans = 0;
int up = min(lim ? t[pos] - '0' : 9, limit);
for (int i = 0; i <= up; ++i) {
ans += dfs(pos + 1, lim && i == (t[pos] - '0'));
}
if (!lim) {
f[pos] = ans;
}
return ans;
};
long long a = dfs(0, true);
t = to_string(finish);
memset(f, -1, sizeof(f));
long long b = dfs(0, true);
return b - a;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48 | func numberOfPowerfulInt(start, finish int64, limit int, s string) int64 {
t := strconv.FormatInt(start-1, 10)
f := make([]int64, 20)
for i := range f {
f[i] = -1
}
var dfs func(int, bool) int64
dfs = func(pos int, lim bool) int64 {
if len(t) < len(s) {
return 0
}
if !lim && f[pos] != -1 {
return f[pos]
}
if len(t)-pos == len(s) {
if lim {
if s <= t[pos:] {
return 1
}
return 0
}
return 1
}
ans := int64(0)
up := 9
if lim {
up = int(t[pos] - '0')
}
up = min(up, limit)
for i := 0; i <= up; i++ {
ans += dfs(pos+1, lim && i == int(t[pos]-'0'))
}
if !lim {
f[pos] = ans
}
return ans
}
a := dfs(0, true)
t = strconv.FormatInt(finish, 10)
for i := range f {
f[i] = -1
}
b := dfs(0, true)
return b - a
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 | function numberOfPowerfulInt(start: number, finish: number, limit: number, s: string): number {
let t: string = (start - 1).toString();
let f: number[] = Array(20).fill(-1);
const dfs = (pos: number, lim: boolean): number => {
if (t.length < s.length) {
return 0;
}
if (!lim && f[pos] !== -1) {
return f[pos];
}
if (t.length - pos === s.length) {
if (lim) {
return s <= t.substring(pos) ? 1 : 0;
}
return 1;
}
let ans: number = 0;
const up: number = Math.min(lim ? +t[pos] : 9, limit);
for (let i = 0; i <= up; i++) {
ans += dfs(pos + 1, lim && i === +t[pos]);
}
if (!lim) {
f[pos] = ans;
}
return ans;
};
const a: number = dfs(0, true);
t = finish.toString();
f = Array(20).fill(-1);
const b: number = dfs(0, true);
return b - a;
}
|