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

题目地址(1638. 统计只差一个字符的子串数目)

https://leetcode.cn/problems/count-substrings-that-differ-by-one-character/

题目描述

给你两个字符串 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:


# 方法 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:


# 方法 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 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。

最后更新于