Python3 - digit DP and KMP
Very similar to the digit DP problem, but this is quite hard in my opinion. There are 2 tricky parts:\n\n1. For slow programming language, it is better to set 2
Very similar to the digit DP problem, but this is quite hard in my opinion. There are 2 tricky parts:\n\n1. For slow programming language, it is better to set 2 restrictions for both lowerbound and upperbound. Otherwise in the worst case, each index will branch out 26 possiblities which is bad to meet timing. See `restrict1` and `restrict2` in the program.\n2. It looks like we need to use KMP along with the DP; this is a bit hard in real interview - you will need to basically memorize how LPS works and how the program is written. There is no time for you to think it out during interview.\n\n```python\nclass Solution:\n    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n        table = {chr(ord(\'a\') +i): i for i in range(26)}\n        MOD = 10 ** 9 + 7\n        memo = defaultdict(int)\n\n        def lps(pat): \n            res = [0]\n            i, target = 1, 0\n            while i < len(pat): \n                if pat[i] == pat[target]: \n                    target += 1\n                    res += target,\n                    i += 1\n                elif target: \n                    target = res[target-1] \n                else: \n                    res += 0,\n                    i += 1\n            return res\n        \n        lps_table = lps(evil)\n        \n        def dp(i, matched, restrict1, restrict2):\n            if matched == len(evil):\n                return 0\n            if i == n:\n                return 1\n            if (i, matched, restrict1, restrict2) not in memo:\n                limit1 = 0 if not restrict1 else table[s1[i]]\n                limit2 = 25 if not restrict2 else table[s2[i]]\n                for j in range(limit1, limit2 + 1):\n                    new1 = restrict1 and j == limit1\n                    new2 = restrict2 and j == limit2\n                    nxt_matched, c = matched, chr(ord(\'a\') + j)\n                    while evil[nxt_matched] != c and nxt_matched:\n                        nxt_matched = lps_table[nxt_matched - 1]\n                    nxt_matched += (c == evil[nxt_matched])\n                    memo[i, matched, restrict1, restrict2] += \\\n                        dp(i+1, nxt_matched, new1, new2)\n                memo[i, matched, restrict1, restrict2] %= MOD\n            return memo[i, matched, restrict1, restrict2]\n\n        return dp(0, 0, True, True)\n```
[]