Find All Good Strings LeetCode solution in Python

1
from functools import lru_cache
2

3

4
class Solution:
5
    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
6
        def srange(a, b):
7
            return [chr(i) for i in range(ord(a), ord(b) + 1)]
8

9
        def LPS(pat):
10
            lps = [0]
11
            i, target = 1, 0
12
            while i < len(pat):
13
                if pat[i] == pat[target]:
14
                    target += 1
15
                    lps.append(target)
16
                    i += 1
17
                elif target:
18
                    target = lps[target - 1]
19
                else:
20
                    lps.append(0)
21
                    i += 1
22
            return lps
23

24
        lps = LPS(evil)
25
        M = 10**9 + 7
26

27
        @lru_cache(None)
28
        def dfs(i, max_matched_idx, lb, rb):
29
            if max_matched_idx == len(evil):
30
                return 0
31
            if i == n:
32
                return 1
33
            l = s1[i] if lb else "a"
34
            r = s2[i] if rb else "z"
35
            candidates = srange(l, r)
36
            res = 0
37
            for j, c in enumerate(candidates):
38
                nxt_matched_idx = max_matched_idx
39
                while evil[nxt_matched_idx] != c and nxt_matched_idx:
40
                    nxt_matched_idx = lps[nxt_matched_idx - 1]
41
                res = (
42
                    res
43
                    + dfs(
44
                        i + 1,
45
                        nxt_matched_idx + (c == evil[nxt_matched_idx]),
46
                        lb=(lb and j == 0),
47
                        rb=(rb and j == len(candidates) - 1),
48
                    )
49
                ) % M
50
            return res
51

52
        return dfs(0, 0, True, True)