[Python] Top Down DP
Approach:\n\n\nIntro: (click to show)\n\ns1 and s2 are the same length (n characters long).\nSo we will build a n character long string one character at a time.
**Approach:**\n<details>\n\n<summary><b>Intro:</b> (click to show)</summary>\n\ns1 and s2 are the same length (n characters long).\nSo we will build a n character long string one character at a time.\nThe trick is to only use characters that will lead to a good string.\nThis means staying within the bounds of s1 and s2 and avoiding evil substrings.\n\n</details>\n\n<br>\n\n<details>\n\n<summary><b>\u21B9 Lower and upper bounds:</b> (click to show)</summary>\n\nThis means the character cannot make the word "greater" than s2 or "smaller" than s1.  (we will worry about handling "evil" substrings later)\nWe can use lower (lb) and upper (ub) to keep track of what characters are available.  \n\n```s1 = "bat" ; s2 = "dog"```\n\nWhen i = 0 ```lb = "b"``` and ```ub = "d"``` meaning only "b", "c", or "d" are allowed for our first character.  \nIf we choose "a", the string will be smaller than s1 and if we choose "e" the string will be larger than s2.\n\nIf the first character chosen is "b" then our lower bound becomes "a" (the next character in "bat") and our upper bound "z".\nIf this seems odd, consider "ba", "bb", ... "bz".  \nBecause the character is smaller than the upper bound, it is now impossible to make a word larger than s2.\n\nIf the first chracter chosen is "c" then our lower bound becomes "a" (the lowest character in the alphabet) and our upper bound becomes "z".\nBecause "c" is higher than the lower bound and lower than the upper bound, we can choose any lowercase character for the remaining characters.\n\nIf the first character chosen is "d" then our lower bound becomes "a" (the lowest character in the alphabet) \nand our upper bound becomes "o" (the next character in "dog".  \n\nIn the script ```lb``` and ```ub``` are booleans.\nIf ```lb = True``` then we cannot pick a character **less than** s1[i].\nif ```ub = True``` then we cannot pick a character **greater than** s2[i].\n\nIf ```lb = False``` for any character, all subsequent characters will be free from the lower bound (can choose as low as letter \'a\')\nIf ```ub = False``` for any character, all subsequent characters will be free from the upper bound (can choose as high as letter \'z\')\n\n</details>\n\n<br>\n\n<details>\n\n<summary><b>\uD83D\uDE08 Dealing with evil strings:</b> (click to show)</summary>\n\nFor evil strings, we do not need to keep track of the characters used so far.\nInstead we have a second index ```e``` which refers to the character ```evil[e]```.  \n\nWhile building a good string, \n\nRegarding evil substrings, there are two possible cases when we pick a character:\n\n1. If the character matches ```evil[e]``` then increase ```e``` by 1.\nOnce ```e == len(evil)``` we have accidentally built an evil substring so return 0.\n\n2. If the character does not match ```evil[e]``` then reset ```e```.\nHowever... it is not as easy as setting ```e = 0``` and here is why.\n\n```html5\n    Consider evil = "abcdabgg" and your string so far is "...abcdab"\n                     01234567\n    This means e = 5.\n    Now the next character you pick is "c" so string = "...abcdabc"\n    Because we did not pick "g", we broke the evil substring.... but e does not equal zero.\n    The current string ends with "abc" so the 0th, 1st and 2nd index overlap with the prefix of evil.  \n    This means e = 2.  \n```\n\n**So how do we know what to set ```e``` to when the character does not match ```evil[e]```?**\n\nWell, we have 2 pieces of information that we can use:\n\n1. We know that the last ```e``` characters in the good string are equal to ```evil[:e]```\n2. and we know the character (```char```) that we just added to the good string.\n\nThis means the last ```e+1``` characters of the current string are ```evil[:e] + char```.\nWe need to know how many of these overlap with the prefix of ```evil```.  \n```html5\ni.e. evil =     "abcdabgg"   # the first 3 characters (index 0, 1, 2) overlap with the \nstring = "...abcdabc"        # last 3 characters of the current string\n```\n\nWe can quickly find how many (if any) characters overlap with the prefix of evil using a Trie.\n\n</details>\n\n<br>\n\n<details>\n\n<summary><b>Using a Trie:</b> (click to show)</summary>\n\nThe idea here to to use a Trie to find out how much of the **suffix of the good string** overlaps with the **prefix of the evil string.**\n\nTo accomplish this, insert the **reversed prefixes** of the evil string into the trie.  \nThe list in the image below contains all of the reversed prefixes of the evil string.\nThe sketch is what the trie looks like after inserting the reversed prefixes.  (green nodes mark the end of an inserted string)\n\n<img src="https://assets.leetcode.com/users/images/23bbd9e6-55aa-4cb5-a4b8-51d3b9b38df0_1605746962.5368729.png" width="50%">\n\nThen pass the **reversed suffix** of the current string (```"cbadcba"```)into the trie.\nThe deepest tail node (green node) is the maximum prefix overlap.\nIn this case, the deepest node is at depth 2 (where {a,b,c,d,r} are at depth 0).  \n\n</details>\n\n<br>\n\n<details>\n\n<summary><b>Trie Class:</b> (click to show)</summary>\n\n```python\nclass Node(object):\n    def __init__(self, val):\n        self.val = val\n        self.children = {}\n        self.tail = False\n        \nclass Trie(object):\n    def __init__(self, evil):\n        self.root = Node(None)\n        self.evil = evil\n    \n    def insert(self, string):\n        curr = self.root\n        for char in string:\n            if char not in curr.children:\n                curr.children[char] = Node(char)\n            curr = curr.children[char]\n        curr.tail = True\n    \n    @functools.lru_cache(None)\n    def max_overlap(self, e, new_char):\n        curr = self.root.children[new_char]\n        res = int(curr.tail)\n        overlap = 1\n        for char in reversed(self.evil[:e]):\n            if char in curr.children:\n                overlap += 1\n                curr = curr.children[char]\n            else:\n                break\n            if curr.tail:\n                res = overlap\n        return res\n```\n\n</details>\n\n<br>\n\n**Solution:**\n```python\nclass Solution:\n    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n        \n        @functools.lru_cache(None)\n        def helper(i, e, lb, ub):\n            if e == len(evil):\n                return 0\n            if i == n:\n                return 1\n            \n            ways = 0\n            evil_char = ord(evil[e])\n            low, high = ord(s1[i]), ord(s2[i])\n            \n            for char in range(low if lb else 97, high+1 if ub else 123):\n                if char == evil_char:\n                    ways += helper(i+1, e+1, lb and char == low, ub and char == high)\n                else:\n                    new_e = evil_tree.max_overlap(e, chr(char)) if (chr(char) in evil_tree.root.children) else 0\n                    ways += helper(i+1, new_e, lb and char == low, ub and char == high)\n                    \n            return ways\n        \n        evil_tree = Trie(evil)\n        for i in range(1, len(evil) + 1):\n            evil_tree.insert(reversed(evil[:i]))\n            \n        MOD = 10**9 + 7\n        return helper(0, 0, True, True) % MOD\n```
[]