# 1638. 统计只差一个字符的子串数目
### 题目地址(1638. 统计只差一个字符的子串数目)
### 题目描述
```
给你两个字符串 s 和 t ，请你找出 s 中的非空子串的数目，这些子串满足替换 一个不同字符 以后，是 t 串的子串。换言之，请你找到 s 和 t 串中 恰好 只有一个字符不同的子字符串对的数目。
比方说， "computer" and "computation" 只有一个字符不同： 'e'/'a' ，所以这一对子字符串会给答案加 1 。
请你返回满足上述条件的不同子字符串对数目。
一个 子字符串 是一个字符串中连续的字符。
示例 1：
输入：s = "aba", t = "baba"
输出：6
解释：以下为只相差 1 个字符的 s 和 t 串的子字符串对：
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
加粗部分分别表示 s 和 t 串选出来的子字符串。
示例 2：
输入：s = "ab", t = "bb"
输出：3
解释：以下为只相差 1 个字符的 s 和 t 串的子字符串对：
("ab", "bb")
("ab", "bb")
("ab", "bb")
加粗部分分别表示 s 和 t 串选出来的子字符串。
示例 3：
输入：s = "a", t = "a"
输出：0
示例 4：
输入：s = "abe", t = "bbc"
输出：10
提示：
1 <= s.length, t.length <= 100
s 和 t 都只包含小写英文字母。
```
### 前置知识
* 枚举
* 递推
* 动态规划
### 公司
* 暂无
### 暴力枚举
#### 思路
枚举 s 和 t 的所有子串。我们可以通过枚举 s 和 t 的子串开始位置 i 和 j，这需要 $m \* n$ 的时间， 其中 m 和 n 分别为 s 和 t 的长度。
接下来，我们只需要从 i 和 j 开始逐位匹配，即枚举子串长度 k，由于两个子串长度相同， 因此一个 k 就够了。
如果 s\[i+k-1] == t\[j+k-1] 不同， 那么 diff + 1，如果 diff 等于 1（意味着两个子串只有一个字符不同），那么答案加 1，最后返回答案即可。
#### 关键点
* 枚举 s 和 t 的起点 i 和 j， 接下来枚举子串长度 k
#### 代码
* 语言支持：Python3
Python3 Code:
```python
# 方法 1
class Solution:
def countSubstrings(self, s: str, t: str) -> int:
m, n = len(s), len(t)
ans = 0
for i in range(m):
for j in range(n):
diff = 0
k = 0
while i + k < m and j + k < n:
diff += int(s[i + k] != t[j + k])
if diff > 1:
break
if diff == 1:
ans += 1
k += 1
return ans
```
**复杂度分析**
令 m, n 为 s 和 t 的长度。
* 时间复杂度：$O(m \* n \* min(m, n))$
* 空间复杂度：$O(1)$
### 递推 + 枚举
#### 思路
这个思路主要是通过空间换时间， 换的是内层枚举 k 的时间。
上面的思路枚举的 s 和 t 的起点， 这个思路是枚举 s 和 t 的字符不同的点 i 和 j（即中间的点），然后向左找能够**完全匹配的长度**，然后向右找能够**完全匹配的长度**，这两个长度相乘就等于以 s\[i] 和 t\[j] 为不同字符的子串个数。
如果求向左和向右的**完全匹配的长度** 呢?
可以利用递推实现。定义 L\[i]\[j] 为以 s\[i] 和 t\[j] 为不同字符向左完全匹配个数。 如果 s\[i] 和 t\[j] 相同， 那么 L\[i]\[j] 就为 0，否则 L\[i]\[j] 为 L\[i-1]\[j-1] + 1
向右匹配同理。
#### 关键点
* 枚举不同的那个字符，向左向右扩展
#### 代码
* 语言支持：Python3
Python3 Code:
```python
# 方法 2
class Solution:
def countSubstrings(self, s: str, t: str) -> int:
L = [[0] * (len(t)+1) for _ in range(len(s)+1)] # L[i][j] 表示 s[i] != s[j] 情况下可以向左扩展的最大长度
R = [[0] * (len(t)+1) for _ in range(len(s)+1)] # R[i][j] 表示 s[i] != s[j] 情况下可以向右扩展的最大长度
ans = 0
for i in range(1,len(s)+1):
for j in range(1,len(t)+1):
if s[i-1] != t[j-1]:
L[i][j] = 0
else:
L[i][j] = L[i-1][j-1] + 1
for i in range(len(s)-1,-1,-1):
for j in range(len(t)-1,-1,-1):
if s[i] != t[j]:
R[i][j] = 0
else:
R[i][j] = R[i+1][j+1] + 1
# 枚举不同的那个字符，这样就只需向左向右匹配即可
for i in range(len(s)):
for j in range(len(t)):
# L 前面有哨兵，因此 L[i][j] 相当于没有哨兵的 L[i-1][j-1]
if s[i] != t[j]: ans += (L[i][j] + 1) * (R[i+1][j+1] + 1)
return ans
```
**复杂度分析**
令 m, n 为 s 和 t 的长度。
* 时间复杂度：$O(m \* n)$
* 空间复杂度：$O(m \* n)$
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/1638.count-substrings-that-differ-by-one-character.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.