[Python3] Digit DP + KMP - Simple Solution
Intuition\n Describe your first thoughts on how to solve this problem. \n- Find the total numbers of string in range that satisfy 2 condions: one is smaller or 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- Find the total numbers of string in range that satisfy 2 condions: one is smaller or equal something threshhold and the other is a specific condition -> Digit DP.\n- It mostly works like any other digit dp problem. However the hard part of any Digit DP problem is the other specific conditions.\n- In this problem determine whether current string contain some substring of `evil` is hard. It is hard to determine and I was struggle much time to figure it out.\n\n# Approach\n- we use the parameter `match_number` to keep the longest substring of `evil` from the beginning to the character similar to current character.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(N * 2 * M * 26)$$ ~ $$O(N * M)$$ with `N` is `n` and `M` is lenght of `evil`\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(N * 2 * M)$$ ~ $$O(N * M)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\nclass Solution:\n    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n        mod = 10 ** 9 + 7\n        def convert_str_to_num(s: str) -> int:\n            return ord(s) - ord("a")\n        \n        num1, num2, evil_num = list(map(convert_str_to_num, s1)), tuple(map(convert_str_to_num, s2)), tuple(map(convert_str_to_num, evil))\n        def prefix_function(tup: tuple) -> List[int]:\n            l = len(tup)\n            lps = [0 for _ in range(l)]\n            for i in range(1, l):\n                j = lps[i - 1]\n                while j > 0 and tup[i] != tup[j]: j = lps[j - 1]\n                if tup[i] == tup[j]: j += 1\n                lps[i] = j\n            return lps\n\n        kmp = prefix_function(evil_num)\n\n        @cache\n        def dp(pos: int, tight: True, match_number: int, num: tuple) -> int:\n            if match_number == len(evil_num): return 0\n            if pos == n: return 1\n            res = 0\n            bound = num[pos] if tight else 26\n            for i in range(bound + 1):\n                if i == 26: continue\n                new_tight = i == bound\n                j = match_number\n                while j > 0 and evil_num[j] != i:\n                    j = kmp[j - 1]\n                if evil_num[j] == i: j += 1\n                res = (res + dp(pos + 1, new_tight, j, num))\n            return res % mod\n\n        i = n - 1\n        while i >= 0 and num1[i] == 0:\n            num1[i] = 25\n            i -= 1\n        if i >= 0: num1[i] -= 1\n        else: return dp(0, True, 0, num2) % mod\n        \n        return (dp(0, True, 0, num2) - dp(0, True, 0, tuple(num1))) % mod\n```
['String', 'Dynamic Programming', 'Python3']