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

标签: 哈希表 字符串 动态规划

难度: Medium

给你两个字符串 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 都只包含小写英文字母。

Submission

运行时间: 38 ms

内存: 16.3 MB

class Solution:
    def countSubstrings(self, s: str, t: str) -> int:
        n, m = len(s), len(t)
        s, t = ' ' + s, ' ' + t
        pre = [[0] * (m + 1) for _ in range(n + 1)]
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        res = 0
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                pre[i][j] = pre[i - 1][j - 1] + 1 if s[i] == t[j] else 0
                dp[i][j] = dp[i - 1][j - 1] if s[i] == t[j] else pre[i - 1][j - 1] + 1
                res += dp[i][j]
        return res

Explain

本题解采用动态规划的方法来计算只差一个字符的子串数目。首先，定义两个二维数组 pre 和 dp，其中 pre[i][j] 用于存储字符串 s 和 t 在位置 i 和 j 处前面连续匹配的字符数量。dp[i][j] 用于记录以 s[i] 和 t[j] 结尾且恰好有一个字符不同的子字符串的数量。如果 s[i] 等于 t[j]，那么 dp[i][j] 直接继承 dp[i-1][j-1] 的值；如果不等，则 dp[i][j] 等于 pre[i-1][j-1] + 1（表示之前的匹配字符数量加上当前不匹配的一个字符）。最后，通过遍历 dp 数组并累加其中的值来计算结果。

时间复杂度: O(n*m)

空间复杂度: O(n*m)

class Solution:
    def countSubstrings(self, s: str, t: str) -> int:
        n, m = len(s), len(t)
        s, t = ' ' + s, ' ' + t  # 添加空格使得索引从1开始，简化边界处理
        pre = [[0] * (m + 1) for _ in range(n + 1)]  # pre[i][j] 表示 s 和 t 在 i 和 j 位置的最长前缀匹配长度
        dp = [[0] * (m + 1) for _ in range(n + 1)]  # dp[i][j] 表示以 s[i] 和 t[j] 结尾的子字符串恰好有一个字符不同的数量
        res = 0
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                pre[i][j] = pre[i - 1][j - 1] + 1 if s[i] == t[j] else 0  # 更新前缀匹配长度
                dp[i][j] = dp[i - 1][j - 1] if s[i] == t[j] else pre[i - 1][j - 1] + 1  # 计算 dp 值
                res += dp[i][j]  # 累加结果
        return res  # 返回结果

Explore

`pre[i][j]`表示字符串`s`和字符串`t`在位置`i`和`j`处之前连续匹配的最长字符数量。这个数组帮助跟踪两个字符串的连续匹配长度，这是计算只差一个字符的子字符串数目的基础。`dp[i][j]`表示以`s[i]`和`t[j]`作为结尾的子字符串中恰好有一个字符不同的子字符串数量。这个数组是核心的动态规划状态，用于记录符合条件的子字符串数量，并通过对其进行累加来得到最终的答案。

当`s[i]`与`t[j]`不相等时，这意味着我们发现了一个不匹配的字符。这时，`pre[i-1][j-1]`已经记录了`s`和`t`在`i-1`和`j-1`之前的连续匹配字符数量。通过将这个匹配长度加上当前这一个不匹配的字符（即`+1`），`dp[i][j]`能够反映出以`s[i]`和`t[j]`结尾的子字符串中正好有一个字符不同的情况。这样确保了我们统计的是恰好一个字符不同的子字符串数量。

为了简化边界条件的处理，题解中在字符串`s`和`t`的开始加上了一个空格，使得索引从1开始。这样，`pre`和`dp`数组的初始化可以在索引0处全部设为0。对于`pre[i][0]`和`pre[0][j]`，因为没有字符可以匹配，所以这些值都是0。同样，`dp[i][0]`和`dp[0][j]`也都初始化为0，因为没有足够的长度来形成子字符串。这种初始化确保了在动态规划过程中，所有的边界条件都被自然而然地处理了。