LeetCode 1397 C++ 实现（数位DP + KMP自动机）

这是 C++ 最优解，采用记忆化DP + KMP自动机，代码简洁高效，能直接通过所有测试用例，严格遵循 C++ 工程规范。

完整代码

#include <vector>
#include <string>
#include <cstring>
using namespace std;

const int MOD = 1e9 + 7;

class Solution {
public:
    int n, m;       // n:目标长度  m:evil串长度
    string s1, s2, evil;
    vector<int> nxt;        // KMP next数组
    vector<vector<int>> trans; // KMP转移矩阵
    long long dp[505][55][2][2]; // 记忆化DP数组

    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.size();

        // 1. 预处理KMP
        initNext();
        initTrans();

        // 2. 初始化DP为-1（标记未访问）
        memset(dp, -1, sizeof(dp));

        // 3. 记忆化DFS
        return dfs(0, 0, true, true);
    }

    // 构建KMP next数组
    void initNext() {
        nxt.resize(m, 0);
        int j = 0;
        for (int i = 1; i < m; ++i) {
            while (j > 0 && evil[i] != evil[j]) j = nxt[j-1];
            if (evil[i] == evil[j]) j++;
            nxt[i] = j;
        }
    }

    // 构建KMP状态转移矩阵
    void initTrans() {
        trans.resize(m, vector<int>(26));
        for (int k = 0; k < m; ++k) {
            for (int c = 0; c < 26; ++c) {
                char ch = 'a' + c;
                int j = k;
                while (j > 0 && evil[j] != ch) j = nxt[j-1];
                if (evil[j] == ch) j++;
                trans[k][c] = j;
            }
        }
    }

    // 数位DP核心
    int dfs(int pos, int k, bool tight1, bool tight2) {
        // 匹配到evil串，非法
        if (k == m) return 0;
        // 构造完成，合法字符串+1
        if (pos == n) return 1;
        // 记忆化直接返回
        if (dp[pos][k][tight1][tight2] != -1) 
            return dp[pos][k][tight1][tight2];

        long long res = 0;
        // 当前字符上下界
        char l = tight1 ? s1[pos] : 'a';
        char r = tight2 ? s2[pos] : 'z';

        // 枚举所有合法字符
        for (char c = l; c <= r; ++c) {
            bool newT1 = tight1 && (c == s1[pos]);
            bool newT2 = tight2 && (c == s2[pos]);
            int newK = trans[k][c - 'a'];
            res = (res + dfs(pos+1, newK, newT1, newT2)) % MOD;
        }

        // 存入记忆
        dp[pos][k][tight1][tight2] = res;
        return res;
    }
};

核心知识点

1. KMP 预处理

• next 数组：快速回退匹配位置，避免暴力匹配；
• trans 转移矩阵：提前计算所有状态跳转，DP 中 O(1) 查表，效率拉满。

2. DP 状态定义

dp[pos][k][tight1][tight2]

• pos：当前构造到第几位
• k：当前匹配 evil 的长度（k==m 直接非法）
• tight1：是否受 s1 下界约束
• tight2：是否受 s2 上界约束

3. 关键逻辑

1. 只要匹配到完整 evil 串，直接返回 0；
2. 构造完长度为 n 的合法串，返回 1；
3. 枚举当前位所有在上下界内的字符，递归统计；
4. 所有结果对 1e9+7 取模，防止溢出。

复杂度

• 时间：O(n × m × 26)
• 空间：O(n × m)
  完全适配题目最大数据范围。

总结

1. 这是 C++ 标准最优解，数位DP + KMP 是本题唯一高效解法；
2. memset 快速初始化 DP 数组，比 vector 更高效；
3. 状态转移矩阵让匹配过程变成简单查表。