LeetCode 题解工作台
找到所有好字符串
给你两个长度为 n 的字符串 s1 和 s2 ，以及一个字符串 evil 。请你返回 好字符串 的数目。 好字符串 的定义为：它的长度为 n ，字典序大于等于 s1 ，字典序小于等于 s2 ，且不包含 evil 为子字符串。 由于答案可能很大，请你返回答案对 10^9 + 7 取余的结果。 示例 1…
3
题型
0
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你两个长度为 n 的字符串 s1 和 s2 ，以及一个字符串 evil 。请你返回 好字符串 的数目。
好字符串 的定义为：它的长度为 n ，字典序大于等于 s1 ，字典序小于等于 s2 ，且不包含 evil 为子字符串。
由于答案可能很大，请你返回答案对 10^9 + 7 取余的结果。
示例 1：
输入：n = 2, s1 = "aa", s2 = "da", evil = "b" 输出：51 解释：总共有 25 个以 'a' 开头的好字符串："aa"，"ac"，"ad"，...，"az"。还有 25 个以 'c' 开头的好字符串："ca"，"cc"，"cd"，...，"cz"。最后，还有一个以 'd' 开头的好字符串："da"。
示例 2：
输入：n = 8, s1 = "leetcode", s2 = "leetgoes", evil = "leet" 输出：0 解释：所有字典序大于等于 s1 且小于等于 s2 的字符串都以 evil 字符串 "leet" 开头。所以没有好字符串。
示例 3：
输入：n = 2, s1 = "gx", s2 = "gz", evil = "x" 输出：2
提示：
s1.length == ns2.length == ns1 <= s21 <= n <= 5001 <= evil.length <= 50- 所有字符串都只包含小写英文字母。
解题思路
方法一
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate demonstrates an understanding of dynamic programming with multiple states.
- question_mark
The candidate is able to handle large number computations efficiently with modulo arithmetic.
- question_mark
The candidate should show knowledge of how to avoid building strings directly by using automaton or substring matching techniques.
常见陷阱
外企场景- error
Failing to account for all four states in the dynamic programming transition, leading to incorrect string counting.
- error
Not using modulo arithmetic correctly to handle large numbers, which can result in integer overflow or incorrect answers.
- error
Overcomplicating the solution by trying to generate all possible strings, rather than leveraging DP to solve the problem more efficiently.
进阶变体
外企场景- arrow_right_alt
Modify the problem to allow any substring rather than just evil, and solve it with the same DP approach.
- arrow_right_alt
Extend the problem to support lexicographical range queries across multiple strings with different evil substrings.
- arrow_right_alt
Increase the string length (n) and analyze how the solution scales in terms of performance and complexity.