Python | DFS with LPS Array | KMP | Clean Code
Based on the following two links\nhttps://leetcode.com/problems/find-all-good-strings/discuss/555010/Python-Simple-DFS-with-KMP\nhttps://leetcode.com/problems/f
Based on the following two links\nhttps://leetcode.com/problems/find-all-good-strings/discuss/555010/Python-Simple-DFS-with-KMP\nhttps://leetcode.com/problems/find-all-good-strings/discuss/555591/JavaC%2B%2B-Memoization-DFS-and-KMP-with-Picture-Clean-code-~-12ms\nThe figure in the link above is very important\n\n```\nfrom functools import lru_cache\nclass Solution:\n    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n        def srange(a, b):\n            return [chr(i) for i in range(ord(a),ord(b)+1)]\n        def LPS(pat):\n            lps = [0]\n            i, target = 1, 0\n            while i < len(pat):\n                if pat[i] == pat[target]:\n                    target += 1\n                    lps.append(target)\n                    i += 1\n                elif target:\n                    target = lps[target-1]\n                else:\n                    lps.append(0)\n                    i += 1\n            return lps\n        lps = LPS(evil)\n        M = 10**9+7\n        @lru_cache(None)\n        def dfs(i, max_matched_idx, lb, rb):\n            if max_matched_idx == len(evil): return 0\n            if i == n: return 1\n            l = s1[i] if lb else \'a\'\n            r = s2[i] if rb else \'z\'\n            candidates = srange(l, r)\n            res = 0\n            for j, c in enumerate(candidates):\n                nxt_matched_idx = max_matched_idx\n                while evil[nxt_matched_idx] != c and nxt_matched_idx:\n                    nxt_matched_idx = lps[nxt_matched_idx-1]\n                res = (res + dfs(i+1, nxt_matched_idx+(c==evil[nxt_matched_idx]),\n                          lb = (lb and j == 0), rb = (rb and j==len(candidates)-1)))%M\n            return res\n        return dfs(0, 0, True, True)
['Depth-First Search', 'Python']