class Solution {
public:
int findGoodStrings(int n, string s1, string s2, string evil) {
}
};
1397. 找到所有好字符串
给你两个长度为 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 == ns2.length == ns1 <= s21 <= n <= 5001 <= evil.length <= 50原站题解
cpp 解法, 执行用时: 28 ms, 内存消耗: 7.1 MB, 提交时间: 2023-10-09 10:49:45
class Solution {
private:
// 这是用来帮助计算关于 stats 的转移函数的 fail 数组
vector<int> fail;
// 这是存储动态规划结果的数组
// 维度从左到右分别为 pos, stats, bound
int f[500][50][4];
// 这是存储转移函数结果的数组
// 两个维度分别为 stats 和 d
int trans[50][26];
static constexpr int mod = 1000000007;
string s1, s2, evil;
public:
// 这是计算关于 stats 的转移函数
// 输入为 stats 和 d
// 输出为转移的结果 g_s(stats, d)
int getTrans(int stats, char ch) {
// 如果之前计算过该转移函数就直接返回结果
if (trans[stats][ch - 97] != -1) {
return trans[stats][ch - 97];
}
// 这是 KMP 算法的一部分
// 把 evil 看作「模式串」，stats 看作「主串」匹配到的位置
while (stats && evil[stats] != ch) {
stats = fail[stats - 1];
}
// 存储结果并返回
return trans[stats][ch - 97] = (evil[stats] == ch ? stats + 1 : 0);
}
// 这是用来进行记忆化搜索的函数
// 输入为 pos, stats 和 bound
// 输出为 f[pos][stats][bound]
int dfs(int pos, int stats, int bound) {
// 如果匹配到了 evil 的末尾
// 说明字符串不满足要求了
// 返回 0
if (stats == evil.size()) {
return 0;
}
// 如果匹配到了上下界的末尾
// 说明找到了一个满足要求的字符串
// 返回 1
if (pos == s1.size()) {
return 1;
}
// 记忆化搜索的关键
// 如果之前计算过该状态就直接返回结果
if (f[pos][stats][bound] != -1) {
return f[pos][stats][bound];
}
// 将当前状态初始化
// 因为未初始化的状态值为 -1
f[pos][stats][bound] = 0;
// 计算第 pos 位可枚举的字符下界
char l = (bound & 1 ? s1[pos] : 'a');
// 计算第 pos 位可枚举的字符上界
char r = (bound & 2 ? s2[pos] : 'z');
for (char ch = l; ch <= r; ++ch) {
int nxt_stats = getTrans(stats, ch);
// 这里写得较为复杂
// 本质上就是关于 bound 的转移函数
// 可以根据自己的理解编写
int nxt_bound = (bound & 1 ? ch == s1[pos] : 0) ^ (bound & 2 ? (ch == s2[pos]) << 1 : 0);
f[pos][stats][bound] += dfs(pos + 1, nxt_stats, nxt_bound);
f[pos][stats][bound] %= mod;
}
return f[pos][stats][bound];
}
int findGoodStrings(int n, string _s1, string _s2, string _evil) {
s1 = _s1;
s2 = _s2;
evil = _evil;
int m = evil.size();
fail.resize(m);
// 这是 KMP 算法的一部分
// 把「evil」看作模式串，得到它的 fail[] 数组
for (int i = 1; i < m; ++i) {
int j = fail[i - 1];
while (j && evil[j] != evil[i]) {
j = fail[j - 1];
}
if (evil[j] == evil[i]) {
fail[i] = j + 1;
}
}
// 将未搜索过的动态规划状态置为 -1
memset(f, -1, sizeof(f));
// 将未计算过的转移函数置为 -1
memset(trans, -1, sizeof(trans));
// 答案即为 f[0][0][3]
return dfs(0, 0, 3);
}
};
java 解法, 执行用时: 34 ms, 内存消耗: 42.6 MB, 提交时间: 2023-10-09 10:49:18
class Solution {
int[] fail;
// 这是存储动态规划结果的数组
// 维度从左到右分别为 pos, stats, bound
int[][][] f;
// int f[500][50][4];
// 这是存储转移函数结果的数组
// 两个维度分别为 stats 和 d
int[][] trans;
static final int MOD = 1000000007;
String s1, s2, evil;
public int findGoodStrings(int n, String s1, String s2, String evil) {
this.s1 = s1;
this.s2 = s2;
this.evil = evil;
int m = evil.length();
fail = new int[m];
// 这是 KMP 算法的一部分
// 把「evil」看作模式串，得到它的 fail[] 数组
for (int i = 1; i < m; ++i) {
int j = fail[i - 1];
while (j != 0 && evil.charAt(j) != evil.charAt(i)) {
j = fail[j - 1];
}
if (evil.charAt(j) == evil.charAt(i)) {
fail[i] = j + 1;
}
}
// 将未搜索过的动态规划状态置为 -1
f = new int[n][m][4];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
Arrays.fill(f[i][j], -1);
}
}
// 将未计算过的转移函数置为 -1
trans = new int[m][26];
for (int i = 0; i < m; ++i) {
Arrays.fill(trans[i], -1);
}
// 答案即为 f[0][0][3]
return dfs(0, 0, 3);
}
// 这是用来进行记忆化搜索的函数
// 输入为 pos, stats 和 bound
// 输出为 f[pos][stats][bound]
public int dfs(int pos, int stats, int bound) {
// 如果匹配到了 evil 的末尾
// 说明字符串不满足要求了
// 返回 0
if (stats == evil.length()) {
return 0;
}
// 如果匹配到了上下界的末尾
// 说明找到了一个满足要求的字符串
// 返回 1
if (pos == s1.length()) {
return 1;
}
// 记忆化搜索的关键
// 如果之前计算过该状态就直接返回结果
if (f[pos][stats][bound] != -1) {
return f[pos][stats][bound];
}
// 将当前状态初始化
// 因为未初始化的状态值为 -1
f[pos][stats][bound] = 0;
// 计算第 pos 位可枚举的字符下界
char l = ((bound & 1) != 0 ? s1.charAt(pos) : 'a');
// 计算第 pos 位可枚举的字符上界
char r = ((bound & 2) != 0 ? s2.charAt(pos) : 'z');
for (char ch = l; ch <= r; ++ch) {
int nxt_stats = getTrans(stats, ch);
// 这里写得较为复杂
// 本质上就是关于 bound 的转移函数
// 可以根据自己的理解编写
int nxt_bound = ((bound & 1) != 0 ? (ch == s1.charAt(pos) ? 1 : 0) : 0) ^ ((bound & 2) != 0 ? (ch == s2.charAt(pos) ? 1 : 0) << 1 : 0);
f[pos][stats][bound] += dfs(pos + 1, nxt_stats, nxt_bound);
f[pos][stats][bound] %= MOD;
}
return f[pos][stats][bound];
}
// 这是计算关于 stats 的转移函数
// 输入为 stats 和 d
// 输出为转移的结果 g_s(stats, d)
public int getTrans(int stats, char ch) {
// 如果之前计算过该转移函数就直接返回结果
if (trans[stats][ch - 'a'] != -1) {
return trans[stats][ch - 'a'];
}
// 这是 KMP 算法的一部分
// 把 evil 看作「模式串」，stats 看作「主串」匹配到的位置
while (stats != 0 && evil.charAt(stats) != ch) {
stats = fail[stats - 1];
}
// 存储结果并返回
return trans[stats][ch - 'a'] = (evil.charAt(stats) == ch ? stats + 1 : 0);
}
}
python3 解法, 执行用时: 408 ms, 内存消耗: 21.6 MB, 提交时间: 2023-10-09 10:48:52
class Solution:
"""@lru_cache 装饰器是 Python 语言提供的可供记忆化搜索的利器
相当于将该参数的（输入，输出）对缓存起来
在以相同的输入调用该函数时，就可以避免计算，直接返回输出
"""
def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
@lru_cache(None)
def getTrans(stats, ch):
"""这是计算关于 stats 的转移函数
输入为 stats 和 d
输出为转移的结果 g_s(stats, d)"""
u = ord(ch) - 97
# 这是 KMP 算法的一部分
# 把 evil 看作「模式串」，stats 看作「主串」匹配到的位置
while stats > 0 and evil[stats] != ch:
stats = fail[stats - 1]
return stats + 1 if evil[stats] == ch else 0
@lru_cache(None)
def dfs(pos, stats, bound):
"""这是用来进行记忆化搜索的函数
输入为 pos, stats 和 bound
输出为 f[pos][stats][bound]"""
# 如果匹配到了 evil 的末尾
# 说明字符串不满足要求了
# 返回 0
if stats == len(evil):
return 0
# 如果匹配到了上下界的末尾
# 说明找到了一个满足要求的字符串
# 返回 1
if pos == len(s1):
return 1
ans = 0
# 计算第 pos 位可枚举的字符下界
l = (ord(s1[pos]) if bound & 1 else ord('a'))
# 计算第 pos 位可枚举的字符上界
r = (ord(s2[pos]) if bound & 2 else ord('z'))
for u in range(l, r + 1):
ch = chr(u)
nxt_stats = getTrans(stats, ch)
# 这里写得较为复杂
# 本质上就是关于 bound 的转移函数
# 可以根据自己的理解编写
nxt_bound = (ch == s1[pos] if bound & 1 else 0) ^ ((ch == s2[pos]) << 1 if bound & 2 else 0)
ans += dfs(pos + 1, nxt_stats, nxt_bound)
return ans % 1000000007
m = len(evil)
# 这是用来帮助计算关于 stats 的转移函数的 fail 数组
fail = [0] * m
# 这是 KMP 算法的一部分
# 把「evil」看作模式串，得到它的 fail[] 数组
for i in range(1, m):
j = fail[i - 1]
while j > 0 and evil[j] != evil[i]:
j = fail[j - 1]
if evil[j] == evil[i]:
fail[i] = j + 1
# 答案即为 f[0][0][3]
return dfs(0, 0, 3)
python3 解法, 执行用时: 612 ms, 内存消耗: 23.6 MB, 提交时间: 2023-10-09 10:47:45
class Solution:
def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
a=ord('a')
z=ord('z')
arr_e=list(map(ord,evil))
len_e=len(evil)
next=[0]*len_e
for i in range(1,len_e):
j=next[i-1]
while j>0 and evil[i]!=evil[j]:
j=next[j-1]
if evil[i]==evil[j]:
next[i]=j+1
def good(s):
arr=list(map(ord,s))
len_a=len(arr)
@cache
def f(i,skip,reach,e):
if e==len_e:
return 0
if i==len_a:
return 0 if skip else 1
limit=arr[i] if reach else z
ans=0
if skip:
ans+=f(i+1,True,False,0)
for c in range(a,limit+1):
ee=e
while ee>0 and arr_e[ee]!=c:
ee=next[ee-1]
if arr_e[ee]==c:
ee+=1
ans+=f(i+1,False,reach and c==limit,ee)
return ans%int(1e9+7)
return f(0,True,True,0)
return (good(s2)-good(s1)+int(evil not in s1))%int(1e9+7)
java 解法, 执行用时: 14 ms, 内存消耗: 39.5 MB, 提交时间: 2023-10-09 10:46:57
// 数位dp + kmp
class Solution {
int n;
int[][] dp;
int[] next;
int MOD = (int)1e9 + 7;
public int findGoodStrings(int n, String s1, String s2, String evil) {
this.n = n;
int len = evil.length();
dp = new int[n][len];
for(int i = 0; i < n; i++) {
Arrays.fill(dp[i], -1);
}
next = new int[len];
for(int j = 0, i = 1; i < len; i++) {
while(j > 0 && evil.charAt(i) != evil.charAt(j)) j = next[j - 1];
if(evil.charAt(i) == evil.charAt(j)) j++;
next[i] = j;
}
return dfs(s1, s2, evil, 0, 0, true, true);
}
public int dfs(String s1, String s2, String evil, int i, int j, boolean downLimited, boolean upLimited) {
// 代表字符串中出现了 evil
if(j == evil.length()) return 0;
if(i == n) return 1;
if(!downLimited && !upLimited && dp[i][j] != -1) return dp[i][j];
long ans = 0;
char down = downLimited ? s1.charAt(i) : 'a', up = upLimited ? s2.charAt(i) : 'z';
for(char k = down; k <= up; k++) {
int nj = j;
while(nj > 0 && k != evil.charAt(nj)) nj = next[nj - 1];
// 此处要注意，当 nj == 0 的时候，会存在 k != evil.charAt(nj) 的情况
// 若直接 nj + 1 进入递归，是认为此时的两个字符一定是匹配上了，实际上可能并没有
if(nj == 0 && k != evil.charAt(nj)) nj = -1;
ans = (ans + dfs(s1, s2, evil, i + 1, nj + 1, downLimited && k == down, upLimited && k == up)) % MOD;
}
if(!downLimited && !upLimited) dp[i][j] = (int)ans;
return (int)ans;
}
}