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

这是 Go 语言标准最优解，采用记忆化DFS + KMP自动机，代码简洁、效率拉满，直接通过所有测试用例。

完整代码

package main

const mod = 1e9 + 7

func findGoodStrings(n int, s1 string, s2 string, evil string) int {
	m := len(evil)
	// 1. 预处理KMP next数组
	nxt := getNext(evil)
	// 2. 预处理KMP状态转移矩阵
	trans := getTrans(evil, nxt)

	// 记忆化DP数组：dp[pos][k][tight1][tight2]
	// pos: 0~n, k:0~m, tight1/tight2:0/1
	dp := make([][][][]int, n)
	for i := range dp {
		dp[i] = make([][][]int, m)
		for j := range dp[i] {
			dp[i][j] = make([][]int, 2)
			for k := range dp[i][j] {
				dp[i][j][k] = []int{-1, -1}
			}
		}
	}

	// DFS函数定义
	var dfs func(pos, k int, tight1, tight2 bool) int
	dfs = func(pos, k int, tight1, tight2 bool) int {
		// 匹配到evil串，直接返回0（非法）
		if k == m {
			return 0
		}
		// 构造完成，返回1（合法）
		if pos == n {
			return 1
		}

		// 转换为数字索引
		t1, t2 := 0, 0
		if tight1 {
			t1 = 1
		}
		if tight2 {
			t2 = 1
		}
		// 记忆化直接返回
		if dp[pos][k][t1][t2] != -1 {
			return dp[pos][k][t1][t2]
		}

		res := 0
		// 当前字符上下界
		low := byte('a')
		if tight1 {
			low = s1[pos]
		}
		high := byte('z')
		if tight2 {
			high = s2[pos]
		}

		// 枚举所有合法字符
		for c := low; c <= high; c++ {
			newT1 := tight1 && (c == s1[pos])
			newT2 := tight2 && (c == s2[pos])
			// KMP状态转移
			newK := trans[k][c-'a']
			// 递归累加结果
			res = (res + dfs(pos+1, newK, newT1, newT2)) % mod
		}

		// 存入记忆
		dp[pos][k][t1][t2] = res
		return res
	}

	// 从第0位开始，初始匹配长度0，同时受上下界约束
	return dfs(0, 0, true, true)
}

// getNext 构建KMP失配数组
func getNext(pattern string) []int {
	m := len(pattern)
	nxt := make([]int, m)
	j := 0
	for i := 1; i < m; i++ {
		for j > 0 && pattern[i] != pattern[j] {
			j = nxt[j-1]
		}
		if pattern[i] == pattern[j] {
			j++
			nxt[i] = j
		}
	}
	return nxt
}

// getTrans 构建KMP状态转移矩阵
// trans[k][c] = 当前匹配k个字符，下一个字符为c时，新的匹配长度
func getTrans(pattern string, nxt []int) [][]int {
	m := len(pattern)
	trans := make([][]int, m)
	for k := 0; k < m; k++ {
		trans[k] = make([]int, 26)
		for idx := 0; idx < 26; idx++ {
			c := byte('a' + idx)
			j := k
			// KMP回退逻辑
			for j > 0 && pattern[j] != c {
				j = nxt[j-1]
			}
			if pattern[j] == c {
				j++
			}
			trans[k][idx] = j
		}
	}
	return trans
}

核心逻辑讲解

1. KMP 预处理（核心）

• next 数组：解决字符串匹配的回退问题，避免暴力匹配；
• trans 转移矩阵：提前计算所有状态跳转，DP 中直接 O(1) 查表，大幅提升效率。

2. DP 状态定义

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

• pos：当前构造到第几位（0~n）
• k：当前匹配 evil 的长度（k == len(evil) 直接判定非法）
• tight1：是否受 s1 下界约束（保证字符串 ≥ s1）
• tight2：是否受 s2 上界约束（保证字符串 ≤ s2）

3. 关键规则

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

复杂度分析

• 时间复杂度：O(n × m × 26)
• 空间复杂度：O(n × m)
  完全适配题目最大数据范围（n ≤ 500，evil 长度 ≤ 50）。

总结

1. 这是 Go 语言标准高效解法，数位DP + KMP 是本题唯一最优解；
2. 手动初始化四维 DP 数组，比递归缓存更高效；
3. 状态转移矩阵让匹配过程变成简单查表，代码极简。