1397：找到所有好字符串（2666 分）

2020-03-29 约 654 字预计阅读 2 分钟次阅读

力扣第 182 场周赛第 4 题

题目

给你两个长度为 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
所有字符串都只包含小写英文字母。

分析

数位 dp，用 kmp 维护当前匹配 evil 的长度即可

解答

 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


mod = 10**9+7
def kmp(s):
    n = len(s)
    pi,j = [0]*n,0
    for i in range(1,n):
        while j>0 and s[i]!=s[j]:
            j = pi[j-1]
        j += s[i]==s[j]
        pi[i] = j
    return pi              # pi[i]:i结尾的最大真前缀长度

class Solution:
    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
        @cache 
        def dfs(i,st,lbd,ubd):
            if i==n:
                return 1
            res = 0
            up = s2[i] if ubd else 25
            low = s1[i] if lbd else 0
            for x in range(low,up+1):
                j = st
                while j>0 and x!=evil[j]:
                    j = pi[j-1]
                j += x==evil[j]
                if j<len(evil):
                    res += dfs(i+1,j,lbd and x==low,ubd and x==up)
                    res %= mod
            return res

        gen = lambda s: [ord(c)-ord('a') for c in s]
        s1,s2,evil = gen(s1),gen(s2),gen(evil)
        pi = kmp(evil)
        return dfs(0,0,1,1)

338 ms

目录

1397：找到所有好字符串（2666 分）

题目

分析

解答