1397. Find All Good Strings¶
题目信息¶
- 题号:
1397
- 难度:
Hard
- 主题:
数位动态规划、字符串、KMP 自动机
- 原题:
- 重点:
统计长度为
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。