Leetcode 1397:找到所有好字符串(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1397:找到所有好字符串(超详细的解法!!!)

in leetcode with 0 comment

给你两个长度为 n 的字符串 s1s2 ,以及一个字符串 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="1234"s2="1356",那么不考虑evil的情况下,最后的结果就是cnt(<=s2) - cnt(<s1)(其中cnt表示计算数量)。考虑cnt(<s1)会出现什么问题,如果第二位是0,那么形如"10xx",如果第二位是1,那么形如11xx。也就是当前位没有到上界的话,那么后面可以任意取。也因此,对于小于上界的数的后置位"xx"部分会有很多重叠(所以可以使用动态规划)。那么当前位的字符取值范围实际上是由前面一个字符决定的,如果前面字符是可取范围内的最大值,那么当前字符也只能取到可取范围内的最大值;否则,当前字符可以取a~z。例如:

1 3 5 6
    ↑
----------------
pre: 3
当前可以取0 ~ 5
----------------
pre: 0 ~ 2
当前可以取0 ~ 9

接着思考evil,按照前面的思路,我们只需要找到不包含evil并且小于等于s2的所有字符串的数目和不包含evil并且小于s1的所有字符串的数目,那么就可以得到结果cnt(<=s2)-cnt(<s1)。以s2为例,我们在寻找小于等于其字符串的过程中,需要记录当前串的后缀和evil前缀的最大重叠长度,如果当前串的后缀就是evil的话,那么就不用找了,后面的字符都会包含evil。例如:

1 3 5 6
    ↑
-----------
evil: 3 5

我们可以定义函数$f(si,ei,lt)$表示小于等于字符串s并且不包含evil字符串的所有字符串个数,其中si表示遍历到s的位置,ei表示可以匹配evil的最长前缀位置,lt表示si-1位置是不是上界。那么我们可以通过lt判断当前字符的可选范围,然后遍历可选范围内的所有字符串,找到字符结尾的后缀和evil可以匹配的最长前缀位置t,然后以此位置继续找$f(si+1,t+1,lt)$。

最后思考边界条件,如果si==len(s),那么表示找到了一个字符串;如果ei==len(evil),那么表示后缀是evil,其后的所有字符串都包含evil

from functools import lru_cache
class Solution:
    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
        sn, en = len(s1), len(evil)
        mod = 10**9 + 7
        
        ne = [0] * (en + 1)
        ne[0] = j = -1
        i = 0
        while i < en:
            while j != -1 and evil[i] != evil[j]: j = ne[j]
            i += 1
            j += 1
            ne[i] = j
            
        @lru_cache(None)
        def dfs1(si, ei, lt):
            if ei == en: return 0
            if si == sn: return 1
            
            m = s1[si] if lt else 'z'
            res = 0
            for i in range(97, ord(m) + 1):
                t = ei
                while t != -1 and evil[t] != chr(i):
                    t = ne[t]
                res += dfs1(si + 1, t + 1, lt and (i == ord(m))) 
            return res % mod
        
        @lru_cache(None)
        def dfs2(si, ei, lt):
            if ei == en: return 0
            if si == sn: return 1
            
            m = s2[si] if lt else 'z'
            res = 0
            for i in range(97, ord(m) + 1):
                t = ei
                while t != -1 and evil[t] != chr(i):
                    t = ne[t]
                res += dfs2(si + 1, t + 1, lt and (i == ord(m))) 
            return res % mod
        
        res = (dfs2(0, 0, 1) - dfs1(0, 0, 1) + mod) % mod
        if s1.find(evil) == -1: res += 1
        return res

为了编程的方便,我写了两个dfs,分别找小于等于s1(而没有找小于)和小于等于s2的所有字符串个数,所有最后需要判断s1中是不是包含evil

可以将上面的代码继续简化,首先思考当前字符的下界,如果s1串当前字符的前一个字符是上界的话,那么当前字符可以从a开始遍历,也就是a为当前字符的下界;否则,从s1[si]这个字符开始遍历,也就是s1[si]为当前字符的下界。对于当前字符的上界,可以采用前面的讨论。

from functools import lru_cache
class Solution:
    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
        sn, en = len(s1), len(evil)
        mod = 10**9 + 7
        
        ne = [0] * (en + 1)
        ne[0] = j = -1
        i = 0
        while i < en:
            while j != -1 and evil[i] != evil[j]: j = ne[j]
            i += 1
            j += 1
            ne[i] = j
            
        @lru_cache(None)
        def dfs(si=0, ei=0, lt=1, rt=1):
            if ei == en: return 0
            if si == sn: return 1
            
            l = s1[si] if lt else 'a'
            r = s2[si] if rt else 'z'
            res = 0
            for i in range(ord(l), ord(r) + 1):
                t = ei
                while t != -1 and evil[t] != chr(i):
                    t = ne[t]
                res += dfs(si + 1, t + 1, lt and (i == ord(l)), rt and (i == ord(r))) 
            return res % mod
        
        return dfs()

reference:

https://www.bilibili.com/video/BV1U7411D7dh

https://leetcode.com/problems/find-all-good-strings/discuss/555010/Python-Simple-DFS-with-KMP

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses