Python DFS+Memoization
Inspired by @yanrcheng2\'s solution\nWe can generate a DFA array with KMP to fetch the length of longest common substring between a candidate string s and a pre
Inspired by @yanrcheng2\'s [solution](https://leetcode.com/problems/find-all-good-strings/discuss/555010/Python-Simple-DFS-with-KMP)\nWe can generate a DFA array with KMP to fetch the length of longest common substring between a candidate string `s` and a prefix of the evil.\nSo when `evil[i]` doesn\'t match with `s[j]`, we do not need to roll `i` back to 0 but look into DFA and roll it back to the length longest common substring.\n`s` is one potential candidate we generate between `s1` and `s2` and we do not need to instantiate it if we use DFA here).\n\nWhen `i` increase to `len(evil)`, we catch a substring that equals to evil and cannot add it to our counting.\nWhen `j` increase to `n`, we have generated a `s` with no substring equals to evil and add it to our counting.\n\nOne trick part is to decide the range of valid character we can use for the next character of `s` to ensure `s1 <= s <= s2`.\nyanrcheng apply a brilliant way of introducing `lo` and `hi` to determine the lower bound and higher bound of the range. The idea is, if current `lo` is False, we should start from `s1[i]`, else we can start from `a`.\nFor example, let `s1` and `s2` substract with their common prefix, `s1` = "be*", `s2` = "do*". So if `s[0]` is \'b\', `s[1]` should start from `s1[1] = e`. This is the only case when `lo` is False. For other cases, `lo` is True and `s[0]` could be `c` and `s[1]` can start from `a` as "ca*" is a `s` between `s1` and `s2`.\nSame story for `hi`. If `hi` is True, s[i] stick with s2[i]. Otherwise it can end till `z` as "cz*" is a `s` between `s1` and `s2` but `dp*` is not.\nAnd apparently once `lo` / `hi` is True, it\'s True for rest of string. E.g. `caaaa*` is between `be*` and `do*`.\nAnd I use a `bound` whose first bit is `lo` and second bit is `hi`. And `bound` should be a part of memoization.\n```\nclass Solution:\n    def findGoodStrings(self, n, s1, s2, evil):\n        M = 10 ** 9 + 7\n        m = len(evil)\n        memo = {}\n        # use kmp to fetch the length of longest common prefix\n        dfa = [0] * m\n        l = 0\n        for r in range(1, m):\n            while l and evil[l] != evil[r]:\n                l = dfa[l - 1]\n            l += evil[l] == evil[r]\n            dfa[r] = l\n\n        def dfs(i, x, bound):\n            if x == m:\n                return 0\n            if i == n:\n                return 1\n            if (i, x, bound) not in memo:\n                cnt = 0\n                lo = ord(\'a\' if bound & 1 else s1[i])  # "be*" -> {"be*", "ca*", ..}, \'b\' when bound bit = ?0\n                hi = ord(\'z\' if bound & 2 else s2[i])  # "do*" -> {"cz*", "do*", ..}, \'d\' when bound bit = 0?\n                for j, c in enumerate(chr(o) for o in range(lo, hi + 1)):\n                    y = x\n                    while y and evil[y] != c:\n                        y = dfa[y - 1]\n                    y += evil[y] == c\n                    cnt = (cnt + dfs(i + 1, y, bound | (j > 0) | (j < hi - lo) << 1)) % M\n                memo[i, x, bound] = cnt\n            return memo[i, x, bound]\n\t\t\t\n        return dfs(0, 0, 0)\n```
['Python']