#1397

Find All Good Strings

candidate master · 1580 · lc hard +32 · verified · 45.2% accepted · 531 likes · top 28%

⚑ String Matching DP (LCS / Edit Distance)

Description

Given strings s1 and s2 of length n and a forbidden pattern evil, count the number of strings of length n that are lexicographically between s1 and s2 (inclusive) and do not contain evil as a substring. Return the count modulo 10⁹ + 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

Code

1

2

3

class Solution:
    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:

class Solution:
    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int: