1638. 统计只差一个字符的子串数目.md

1638. 统计只差一个字符的子串数目

题目传送门

点击这里

解题思路

这道题题干很好理解，做法是可以从s和t不同的字符位置开始向两侧进行枚举，当接下来再遇到不同的字符，就得到以该位置为中心的满足条件的数对，假如左侧的相同字符个数为l，右侧为r，可以得到满足条件的数对数目为(l + 1) * (r + 1)，用两个数组维护以每个位置结尾和开头的最长相同后缀前缀长度，即f[i][j]表示以(i, j)结尾的最长相同前缀长度，g[i][j]则表示以(i, j)开头的最长相同后缀长度。

代码

func countSubstrings(s string, t string) (ans int) {
	m, n := len(s), len(t)
	f := make([][]int, m+1)
	g := make([][]int, m+1)
	for i := range f {
		f[i] = make([]int, n+1)
		g[i] = make([]int, n+1)
	}
	for i, a := range s {
		for j, b := range t {
			// 当a==b，即(i, j)位置字符相同，即前缀相同字符长度+1
			if a == b {
				f[i+1][j+1] = f[i][j] + 1
			}
		}
	}
	for i := m - 1; i >= 0; i-- {
		for j := n - 1; j >= 0; j-- {
			// 从后开始，同上所属，则后缀相同+1
			if s[i] == t[j] {
				g[i][j] = g[i+1][j+1] + 1
			} else {
				ans += (f[i][j] + 1) * (g[i+1][j+1] + 1)
			}
		}
	}
	return
}