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

LeetCode 1397 C 实现数位DP KMP自动机这是 C最优解采用记忆化DP KMP自动机代码简洁高效能直接通过所有测试用例严格遵循 C 工程规范。完整代码#includevector#includestring#includecstringusingnamespacestd;constintMOD1e97;classSolution{public:intn,m;// n:目标长度 m:evil串长度string s1,s2,evil;vectorintnxt;// KMP next数组vectorvectorinttrans;// KMP转移矩阵longlongdp[505][55][2][2];// 记忆化DP数组intfindGoodStrings(intn,string s1,string s2,string evil){this-nn;this-s1s1;this-s2s2;this-evilevil;this-mevil.size();// 1. 预处理KMPinitNext();initTrans();// 2. 初始化DP为-1标记未访问memset(dp,-1,sizeof(dp));// 3. 记忆化DFSreturndfs(0,0,true,true);}// 构建KMP next数组voidinitNext(){nxt.resize(m,0);intj0;for(inti1;im;i){while(j0evil[i]!evil[j])jnxt[j-1];if(evil[i]evil[j])j;nxt[i]j;}}// 构建KMP状态转移矩阵voidinitTrans(){trans.resize(m,vectorint(26));for(intk0;km;k){for(intc0;c26;c){charchac;intjk;while(j0evil[j]!ch)jnxt[j-1];if(evil[j]ch)j;trans[k][c]j;}}}// 数位DP核心intdfs(intpos,intk,booltight1,booltight2){// 匹配到evil串非法if(km)return0;// 构造完成合法字符串1if(posn)return1;// 记忆化直接返回if(dp[pos][k][tight1][tight2]!-1)returndp[pos][k][tight1][tight2];longlongres0;// 当前字符上下界charltight1?s1[pos]:a;charrtight2?s2[pos]:z;// 枚举所有合法字符for(charcl;cr;c){boolnewT1tight1(cs1[pos]);boolnewT2tight2(cs2[pos]);intnewKtrans[k][c-a];res(resdfs(pos1,newK,newT1,newT2))%MOD;}// 存入记忆dp[pos][k][tight1][tight2]res;returnres;}};核心知识点1. KMP 预处理next数组快速回退匹配位置避免暴力匹配trans转移矩阵提前计算所有状态跳转DP 中O(1)查表效率拉满。2. DP 状态定义dp[pos][k][tight1][tight2]pos当前构造到第几位k当前匹配 evil 的长度km直接非法tight1是否受s1下界约束tight2是否受s2上界约束3. 关键逻辑只要匹配到完整evil串直接返回 0构造完长度为n的合法串返回 1枚举当前位所有在上下界内的字符递归统计所有结果对1e97取模防止溢出。复杂度时间O(n × m × 26)空间O(n × m)完全适配题目最大数据范围。总结这是 C标准最优解数位DP KMP 是本题唯一高效解法memset快速初始化 DP 数组比 vector 更高效状态转移矩阵让匹配过程变成简单查表。