[Python3] dp & kmp ... finally
\n\nclass Solution:\n    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n        lps = [0]\n        k = 0 \n        for i in range(1, le
\n```\nclass Solution:\n    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n        lps = [0]\n        k = 0 \n        for i in range(1, len(evil)): \n            while k and evil[k] != evil[i]: k = lps[k-1]\n            if evil[k] == evil[i]: k += 1\n            lps.append(k)\n        \n        @cache\n        def fn(i, k, lower, upper): \n            """Return number of good strings at position i and k prefix match."""\n            if k == len(evil): return 0 # boundary condition \n            if i == n: return 1 \n            lo = ascii_lowercase.index(s1[i]) if lower else 0\n            hi = ascii_lowercase.index(s2[i]) if upper else 25\n            \n            ans = 0\n            for x in range(lo, hi+1): \n                kk = k \n                while kk and evil[kk] != ascii_lowercase[x]: \n                    kk = lps[kk-1]\n                if evil[kk] == ascii_lowercase[x]: kk += 1\n                ans += fn(i+1, kk, lower and x == lo, upper and x == hi)\n            return ans \n        \n        return fn(0, 0, True, True) % 1_000_000_007\n```
['Python3']