[Python] Simple DFS with KMP
Idea\nThe idea is to DFS all the possible answer and break as early as possible. KMP is used to determined whether the current branch is hopeless efficiently.\n
**Idea**\nThe idea is to DFS all the possible answer and break as early as possible. [KMP](https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm) is used to determined whether the current branch is hopeless efficiently.\n\n**Complexity**\nTime: `O(n * len(evil))`\nSpace: `O(max(n, len(evil)))` for function call stack (worst case)\n\n**Python, DFS with memoization, KMP**\n```\nfrom functools import lru_cache\n\ndef srange(a, b):\n    yield from (chr(i) for i in range(ord(a), ord(b)+1))\n        \ndef failure(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\nclass Solution:\n    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n        f = failure(evil)\n        @lru_cache(None)\n        def dfs(idx, max_matched=0, lb=True, rb=True):\n            \'\'\'\n\t\t\tidx: current_idx_on_s1_&_s2, \n\t\t\tmax_matched: nxt_idx_to_match_on_evil, \n\t\t\tlb, rb: is_left_bound, is_right_bound\n\t\t\t\'\'\'\n            if max_matched == len(evil): return 0 # evil found, break\n            if idx == n: return 1 # base case\n            \n            l = s1[idx] if lb else \'a\' # valid left bound\n            r = s2[idx] if rb else \'z\' # valid right bound\n            candidates = [*srange(l, r)]\n            \n            res = 0\n            for i, c in enumerate(candidates):\n                nxt_matched = max_matched\n                while evil[nxt_matched] != c and nxt_matched:\n                    nxt_matched = f[nxt_matched - 1]\n                res += dfs(idx+1, nxt_matched + (c == evil[nxt_matched]), \n                           lb=(lb and i == 0), rb=(rb and i == len(candidates)-1))\n            return res                \n        \n        return dfs(0) % (10**9 + 7)\n```
['Depth-First Search', 'Graph', 'Python']