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

难度

• Easy
• Medium
• Hard

思路

首先考虑暴力法，看字符串长度为 100，简单估计了下感觉会超时。

然后考虑不同字符出现的位置，可能是开头（其后为连续相同串），中间（两侧为连续相同串），末尾（其前为连续相同串）。

然后……就没有然后了……

打开题解，啪啪打脸。暴力是可以通过的……

看 DP 解法，嗯，枚举不同字符，应该说想的比较接近了。

暴力法没什么说的。

DP 是说，枚举两字符串中不同的字符，用两个二维数组记录不同字符对两侧的连续相同串长度。对于一对不同字符，可以组成的符合条件的子串数量，应当为两侧连续相同串长度加一的积。

代码

暴力

class Solution:
    def countSubstrings(self, s: str, t: str) -> int:
        # 暴力，枚举
        ans = 0
        for i in range(len(s)):
            for j in range(len(t)):
                diff = 0
                k = 0
                while i + k < len(s) and j + k < len(t):
                    if s[i + k] != t[j + k]:
                        diff += 1
                    if diff == 1:
                        ans += 1
                    if diff > 1:
                        break
                    k += 1
        return ans

class Solution:
    def countSubstrings(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        dpl = [[0] * (n + 1) for _ in range(m + 1)]
        dpr = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m):
            for j in range(n):
                if s[i] == t[j]:
                    dpl[i + 1][j + 1] = dpl[i][j] + 1
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if s[i] == t[j]:
                    dpr[i][j] = dpr[i + 1][j + 1] + 1
        ans = 0
        for i in range(m):
            for j in range(n):
                if s[i] != t[j]:
                    ans += (dpl[i][j] + 1) * (dpr[i + 1][j + 1] + 1)
        return ans

其实这里 DP 也没快多少。