找到所有好字符串Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
给你两个长度为 n 的字符串 s1 和 s2 ，以及一个字符串 evil 。请你返回 好字符串 的数目。
好字符串 的定义为：它的长度为 n ，字典序大于等于 s1 ，字典序小于等于 s2 ，且不包含 evil 为子字符串。
由于答案可能很大，请你返回答案对 10^9 + 7 取余的结果。
示例 1：
输入：n = 2, s1 = "aa", s2 = "da", evil = "b"
输出：51
解释：总共有 25 个以 'a' 开头的好字符串："aa"，"ac"，"ad"，...，"az"。还有 25 个以 'c' 开头的好字符串："ca"，"cc"，"cd"，...，"cz"。最后，还有一个以 'd' 开头的好字符串："da"。
示例 2：
输入：n = 8, s1 = "leetcode", s2 = "leetgoes", evil = "leet"
输出：0
解释：所有字典序大于等于 s1 且小于等于 s2 的字符串都以 evil 字符串 "leet" 开头。所以没有好字符串。
示例 3：
输入：n = 2, s1 = "gx", s2 = "gz", evil = "x"
输出：2
提示：
- s1.length == n
- s2.length == n
- s1 <= s2
- 1 <= n <= 500
- 1 <= evil.length <= 50
- 所有字符串都只包含小写英文字母。
# 思路
dfs
# 解法
class Solution {
public int findGoodStrings(int n, String s1, String s2, String evil) {
dp = new int[n+1][evil.length()+1];
next = new int[evil.length()+1];
getNext(evil);
this.n = n;
this.evil = evil;
this.s1 = s1;
this.s2 = s2;
for(int i = 0; i < dp.length; i++)
Arrays.fill(dp[i],-1);
return dfs(0,true,true, 0);
}
StringBuilder cur = new StringBuilder();
int[] next;
int[][] dp ;
int n;
String evil;
String s1,s2;
void getNext(String evil){
int i = 0, j = -1;
next[0]=-1;
while(i < evil.length()-1){
if(j == -1 || evil.charAt(i) == evil.charAt(j)){
++i;
++j;
if(evil.charAt(i) == evil.charAt(j))next[i] = next[j];
else next[i] = j;
}else{
j = next[j];
}
}
}
int mod = (int)1e9+7;
// int indexOf(StringBuilder cur){
// if(cur.length() == 0)return -1;
// int i = 0, j = 0;
// while(i < cur.length() && j < evil.length()){
// if(j == -1 || cur.charAt(i) == evil.charAt(j)){
// ++i;
// ++j;
// }else{
// j = next[j];
// }
// }
// return j == evil.length()? i-evil.length():-1;
// }
// c为尾 在evil字符串中最多匹配多少个
private int getIndx(char c, int num){
while(true){
// 完全不成功
if(num < 0)return 0;
// 匹配成功
else if(evil.charAt(num) == c)return num+1;
else { // 失败 移动
num = next[num];
}
}
}
private int dfs(int i, boolean isUpLimit, boolean isDownLimit,int num){
if(num == evil.length())return 0;
if(i == n)return 1;
if(!isUpLimit && !isDownLimit && dp[i][num] != -1)return dp[i][num];
int res = 0;
int up = isUpLimit? s2.charAt(i):'z';
int down = isDownLimit? s1.charAt(i):'a';
int len = cur.length();
for(int p = down;p <= up; p++){
// cur.append((char) p);
res = ( res + dfs(i+1, isUpLimit && p == up, isDownLimit && p == down, getIndx((char)p, num))) % mod;
// if(res > 0)
// cur.setLength(len);
}
if(!isUpLimit && !isDownLimit)dp[i][num] = res;
return res ;
}
}
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
# 总结
- 分析出几种情况，然后分别对各个情况实现
