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

题目描述

思路及实现

暴力枚举

最开始想到的，就是先确定子串的长度，然后确定在s和t中的拥有这个长度的子串，把它们放入两个列表中，然后对这两个列表进行遍历并将取出的两个子串进行比较，循环结束后得到结果。

class Solution:
    def countSubstrings(self, s: str, t: str) -> int:
        ans = 0
        for i in range(1, len(s) + 1):
            if i > len(t):
                return ans
            tmp_index = 0
            tmp_s = []
            tmp_t = []
            while tmp_index + i <= len(s):
                tmp_s.append(s[tmp_index: tmp_index + i])
                tmp_index += 1
            tmp_index = 0
            while tmp_index + i <= len(t):
                tmp_t.append(t[tmp_index: tmp_index + i])
                tmp_index += 1
            for sub_s in tmp_s:
                for sub_t in tmp_t:
                    dif = 0
                    for cnt in range(0, i):
                        if dif > 1:
                            break
                        if sub_s[cnt] != sub_t[cnt]:
                            dif += 1
                    if dif == 1:
                        ans += 1
        return ans

当然上面代码过于复杂，仔细思考，可以找s和t中不同字符的位置（即s[i] != t[j]），这就满足要找的子串中有一个不同字符的要求了，
然后以这两个位置为中心，向左右扩展，找到左右能延伸的最大距离left和right（即找到s[i - left] != t[j - left]和s[i + right] != t[j + right]为止），
那么对于当前不同字符位置s[i] != t[j]，最多能够构造(left + 1) * (right + 1)个符合要求的子串对。

class Solution:
    def countSubstrings(self, s: str, t: str) -> int:
        ans = 0
        s_len, t_len = len(s), len(t)
        for i in range(len(s)):
            for j in range(len(t)):
                if s[i] != t[j]:
                    left = right = 0
                    while i > left and j > left and s[i - left - 1] == t[j - left - 1]:
                        left += 1
                    while i + right + 1 < s_len and j + right + 1 < t_len and s[i + right + 1] == t[j + right + 1]:
                        right += 1
                    ans += (left + 1) * (right + 1)
        return ans

动态规划

考虑到上面的情况，我们在扩展左右距离时每次都要重复计算left和right，那能否预处理这些数据，需要用的时候直接取出来呢？当然可以。
对于左侧的dpl[i][j]，我们不考虑当前字符s[i]是否等于t[j]，因为我们本来就需要找一个不同字符所以对于dpl[i][j]，应看的是s[i - 1] == t[j - 1] ?。
写出转移方程：

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

---

希望本文章能够帮到您~