Hard

题目描述

给你字符串 s1 和 s2，它们的长度都为 n，以及一个字符串 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"。
最后还有 1 个以 'd' 开头的好字符串："da"。

示例 2：

输入：n = 8, s1 = "leetcode", s2 = "leetgoes", evil = "leet"
输出：0
解释：所有字典序在 s1 和 s2 之间的字符串都以前缀 "leet" 开头，因此没有好字符串。

示例 3：

输入：n = 2, s1 = "gx", s2 = "gz", evil = "x"
输出：2

提示：

  • s1.length == n
  • s2.length == n
  • s1 <= s2
  • 1 <= n <= 500
  • 1 <= evil.length <= 50
  • 所有字符串都只包含小写英文字母

解题思路

这是一道典型的数位动态规划与字符串匹配结合的题目。我们需要解决三个核心问题：

  1. 范围限制：生成的字符串必须在 s1 和 s2 的字典序范围内
  2. 子串匹配：避免包含 evil 作为子字符串
  3. 计数统计：统计满足条件的字符串数量

解题思路：

使用四维动态规划状态 dp[pos][evil_pos][is_s1_prefix][is_s2_prefix]：

  • pos：当前构建到第几个字符位置
  • evil_pos：当前字符串与 evil 的最长公共后缀长度（KMP 中的失配位置）
  • is_s1_prefix：当前字符串是否仍等于 s1 的前缀
  • is_s2_prefix：当前字符串是否仍等于 s2 的前缀

关键技术：

  • 使用 KMP 算法 预处理 evil 字符串的失配函数，用于高效地跟踪匹配状态
  • 当 evil_pos == evil.length() 时，说明完全匹配到了 evil，这种情况需要跳过
  • 通过 is_s1_prefix 和 is_s2_prefix 控制字符选择范围，确保结果在指定区间内

状态转移时，对于每个可选字符，更新 evil 的匹配位置，并根据边界条件更新前缀标志。

代码实现

class Solution {
public:
    int findGoodStrings(int n, string s1, string s2, string evil) {
        const int MOD = 1e9 + 7;
        int m = evil.length();
        
        // KMP preprocessing
        vector<int> failure(m, 0);
        for (int i = 1; i < m; i++) {
            int j = failure[i-1];
            while (j > 0 && evil[i] != evil[j]) {
                j = failure[j-1];
            }
            if (evil[i] == evil[j]) {
                j++;
            }
            failure[i] = j;
        }
        
        // dp[pos][evil_pos][is_s1_prefix][is_s2_prefix]
        vector<vector<vector<vector<int>>>> dp(n+1, vector<vector<vector<int>>>(m+1, 
            vector<vector<int>>(2, vector<int>(2, -1))));
        
        function<int(int, int, bool, bool)> solve = [&](int pos, int evil_pos, bool is_s1_prefix, bool is_s2_prefix) -> int {
            if (evil_pos == m) return 0; // contains evil as substring
            if (pos == n) return 1; // valid string
            
            int& res = dp[pos][evil_pos][is_s1_prefix][is_s2_prefix];
            if (res != -1) return res;
            
            res = 0;
            char start = is_s1_prefix ? s1[pos] : 'a';
            char end = is_s2_prefix ? s2[pos] : 'z';
            
            for (char c = start; c <= end; c++) {
                // Update evil_pos using KMP
                int new_evil_pos = evil_pos;
                while (new_evil_pos > 0 && evil[new_evil_pos] != c) {
                    new_evil_pos = failure[new_evil_pos - 1];
                }
                if (evil[new_evil_pos] == c) {
                    new_evil_pos++;
                }
                
                bool new_is_s1_prefix = is_s1_prefix && (c == s1[pos]);
                bool new_is_s2_prefix = is_s2_prefix && (c == s2[pos]);
                
                res = (res + solve(pos + 1, new_evil_pos, new_is_s1_prefix, new_is_s2_prefix)) % MOD;
            }
            
            return res;
        };
        
        return solve(0, 0, true, true);
    }
};

class Solution:
    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
        MOD = 10**9 + 7
        m = len(evil)
        
        # KMP preprocessing
        failure = [0] * m
        for i in range(1, m):
            j = failure[i-1]
            while j > 0 and evil[i] != evil[j]:
                j = failure[j-1]
            if evil[i] == evil[j]:
                j += 1
            failure[i] = j
        
        from functools import lru_cache
        
        @lru_cache(None)
        def solve(pos, evil_pos, is_s1_prefix, is_s2_prefix):
            if evil_pos == m:
                return 0  # contains evil as substring
            if pos == n:
                return 1  # valid string
            
            result = 0
            start = ord(s1[pos]) if is_s1_prefix else ord('a')
            end = ord(s2[pos]) if is_s2_prefix else ord('z')
            
            for c_ord in range(start, end + 1):
                c = chr(c_ord)
                
                # Update evil_pos using KMP
                new_evil_pos = evil_pos
                while new_evil_pos > 0 and evil[new_evil_pos] != c:
                    new_evil_pos = failure[new_evil_pos - 1]
                if evil[new_evil_pos] == c:
                    new_evil_pos += 1
                
                new_is_s1_prefix = is_s1_prefix and (c == s1[pos])
                new_is_s2_prefix = is_s2_prefix and (c == s2[pos])
                
                result = (result + solve(pos + 1, new_evil_pos, new_is_s1_prefix, new_is_s2_prefix)) % MOD
            
            return result
        
        return solve(0, 0, True, True)

public class Solution {
    private const int MOD = 1000000007;
    private int[,,,] dp;
    private int[] failure;
    private string evil;
    private string s1, s2;
    private int n, m;
    
    public int FindGoodStrings(int n, string s1, string s2, string evil) {
        this.n = n;
        this.s1 = s1;
        this.s2 = s2;
        this.evil = evil;
        this.m = evil.Length;
        
        // KMP preprocessing
        failure = new int[m];
        for (int i = 1; i < m; i++) {
            int j = failure[i-1];
            while (j > 0 && evil[i] != evil[j]) {
                j = failure[j-1];
            }
            if (evil[i] == evil[j]) {
                j++;
            }
            failure[i] = j;
        }
        
        dp = new int[n+1, m+1, 2, 2];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k < 2; k++) {
                    for (int l = 0; l < 2; l++) {
                        dp[i,j,k,l] = -1;
                    }
                }
            }
        }
        
        return Solve(0, 0, 1, 1);
    }
    
    private int Solve(int pos, int evilPos, int isS1Prefix, int isS2Prefix) {
        if (evilPos == m) return 0;
        if (pos == n) return 1;
        
        if (dp[pos, evilPos, isS1Prefix, isS2Prefix] != -1) {
            return dp[pos, evilPos, isS1Prefix, isS2Prefix];
        }
        
        int result = 0;
        char start = isS1Prefix == 1 ? s1[pos] : 'a';
        char end = isS2Prefix == 1 ? s2[pos] : 'z';
        
        for (char c = start; c <= end; c++) {
            int newEvilPos = evilPos;
            while (newEvilPos > 0 && evil[newEvilPos] != c) {
                newEvilPos = failure[newEvilPos - 1];
            }
            if (evil[newEvilPos] == c) {
                newEvilPos++;
            }
            
            int newIsS1Prefix = (isS1Prefix == 1 && c == s1[pos]) ? 1 : 0;
            int newIsS2Prefix = (isS2Prefix == 1 && c == s2[pos]) ? 1 : 0;
            
            result = (result + Solve(pos + 1, newEvilPos, newIsS1Prefix, newIsS2Prefix)) % MOD;
        }
        
        return dp[pos, evilPos, isS1Prefix, isS2Prefix] = result;
    }
}

var findGoodStrings = function(n, s1, s2, evil) {
    const MOD = 1000000007;
    const m = evil.length;
    
    // KMP preprocessing
    const failure = new Array(m).fill(0);
    for (let i = 1; i < m; i++) {
        let j = failure[i-1];
        while (j > 0 && evil[i] !== evil[j]) {
            j = failure[j-1];
        }
        if (evil[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n × m × 26)
空间复杂度O(n × m)

其中 n 是字符串长度，m 是 evil 字符串长度。时间复杂度中的 26 来自于每个位置最多尝试 26 个字符。空间复杂度主要来自记忆化搜索的状态存储。