Description
Given the strings s1
and s2
of size n
and the string evil
, return the number of good strings.
A good string has size n
, it is alphabetically greater than or equal to s1
, it is alphabetically smaller than or equal to s2
, and it does not contain the string evil
as a substring. Since the answer can be a huge number, return this modulo 109 + 7
.
Example 1:
Input: n = 2, s1 = "aa", s2 = "da", evil = "b" Output: 51 Explanation: There are 25 good strings starting with 'a': "aa","ac","ad",...,"az". Then there are 25 good strings starting with 'c': "ca","cc","cd",...,"cz" and finally there is one good string starting with 'd': "da".
Example 2:
Input: n = 8, s1 = "leetcode", s2 = "leetgoes", evil = "leet" Output: 0 Explanation: All strings greater than or equal to s1 and smaller than or equal to s2 start with the prefix "leet", therefore, there is not any good string.
Example 3:
Input: n = 2, s1 = "gx", s2 = "gz", evil = "x" Output: 2
Constraints:
s1.length == n
s2.length == n
s1 <= s2
1 <= n <= 500
1 <= evil.length <= 50
- All strings consist of lowercase English letters.
Solution
Python3
class Solution:
def _kmp(self, pattern: str):
tab = [0] * len(pattern)
j = 0
for i in range(1, len(pattern)):
while j and pattern[i] != pattern[j]:
j = tab[j - 1]
if pattern[i] == pattern[j]:
j += 1
tab[i] = j
return tab
def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
M = 10 ** 9 + 7
E = len(evil)
s1 = [ord(x) - ord('a') for x in s1]
s2 = [ord(x) - ord('a') for x in s2]
kmp = self._kmp(evil)
evil = [ord(x) - ord('a') for x in evil]
@cache
def go(index, evilIndex, tight1, tight2):
if evilIndex == E: return 0
if index == n: return 1
low = s1[index] if tight1 else 0
high = s2[index] if tight2 else 25
res = 0
for char in range(low, high + 1):
nxtTight1 = tight1 and char == s1[index]
nxtTight2 = tight2 and char == s2[index]
j = evilIndex
while j > 0 and evil[j] != char:
j = kmp[j - 1]
if evil[j] == char:
j += 1
res += go(index + 1, j, nxtTight1, nxtTight2)
res %= M
return res
return go(0, 0, True, True)