# 方法 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] 为不同字符的子串个数。
# 方法 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)$
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
