1397. Find All Good Strings

题目信息

题号:

1397

难度:

Hard

主题:

数位动态规划、字符串、KMP 自动机

原题:

LeetCode 1397

重点:

统计长度为 n、字典序位于闭区间 [s1,s2] 且不含 evil 连续子串的字符串数量,并取模

题目重述

给定长度 n 的两个小写字符串 s1、s2,以及小写字符串 evil。好字符串必须长度为 n,字典序不小于 s1 且不大于 s2,并且不能包含 evil 作为连续子串。

请返回好字符串数量对 10^9 + 7 取模后的结果。区间两端都包含在统计中,只要它们自身满足条件。

1 <= n <= 500,s1.length == s2.length == n,1 <= evil.length <= 50。

自建示例

排除区间中含禁用字符的字符串:

输入:n = 2, s1 = "aa", s2 = "ac", evil = "b"
输出:2
解释:候选为 aa、ab、ac,其中 ab 含有 evil,剩余两个合法。

禁用串比目标长度长时不会出现:

输入:n = 1, s1 = "a", s2 = "c", evil = "zz"
输出:3
解释:a、b、c 都不可能包含长度为二的 evil。