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

问题描述#

给你两个字符串 s 和 t ，请你找出 s 中的非空子串的数目，这些子串满足替换 一个不同字符 以后，是 t 串的子串。换言之，请你找到 s 和 t 串中恰好只有一个字符不同的子字符串对的数目。

比方说， "computer" 和 "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 都只包含小写英文字母。

解题思路#

以每一个不相等的字符位置 \(\text{cur}\) 为中心，计算其左右边界 \(\text{left}\) 和 \(\text{right}\)，得到的结果为:

\[ (\text{cur}-\text{left}) + (\text{right}-\text{cur}) + (\text{cur}-\text{left}) * (\text{right}-\text{cur})+1 \]

然后累计每一步的结果即可。

如对于测例：

1 2	`s = "abbab" t = "bbbbb"`

\[ \begin{array}{c|ccc} & b & b & b & b & b \\ \hline a&\color{red}1&\color{blue}1&\color{red}1&\color{blue}1&\color{red}1\\ b&\color{blue}0&\color{red}0&\color{blue}0&\color{red}0&\color{blue}0\\ b&\color{red}0&\color{blue}0&\color{red}0&\color{blue}0&\color{red}0\\ a&\color{blue}1&\color{red}1&\color{blue}1&\color{red}1&\color{blue}1\\ b&\color{red}0&\color{blue}0&\color{red}0&\color{blue}0&\color{red}0 \end{array} \]

字符不相等位置为 1，相等位置为 0。

对于第一个对角线数组 \([1\quad0\quad0\quad1\quad0]\)，

对于第一个出现的 1:

\[ \begin{aligned} &\text{left}=0,\text{cur}=0,\text{right}=2 \\ &(\text{cur}-\text{left}) + (\text{right}-\text{cur}) + (\text{cur}-\text{left}) * (\text{right}-\text{cur})+1=3 \end{aligned} \]

对于第二个出现的 1:

\[ \begin{aligned} &\text{left}=1,\text{cur}=3,\text{right}=4 \\ &(\text{cur}-\text{left}) + (\text{right}-\text{cur}) + (\text{cur}-\text{left}) * (\text{right}-\text{cur})+1=6 \end{aligned} \]

结果为 9。

按照同样的方法得到所有的对角线数组的计算结果为：

\[ \begin{array}{ccccc|l} 1 & 0&0&1&0&\color{red}9 \\\hline 1&0&0&1&&\color{red}6 \\\hline 1&0&0&&&\color{red}3\\\hline 1&0&&&&\color{red}2\\\hline 1&&&&&\color{red}1\\\hline 0&0&1&0&&\color{red}6\\\hline 0&1&0&&&\color{red}4\\\hline 1&0&&&&\color{red}2\\\hline 0&&&&&\color{red}0\\\hline &&&&&\color{red}\mathbf{33} \end{array} \]

class Solution:
    def countSubstrings(self, s: str, t: str) -> int:
        len_s, len_t = len(s), len(t)
        # 对角线起始点即为第一行和第一列的元素
        start_points = [(0, j) for j in range(len_t)] + [
            (i, 0) for i in range(1, len_s)
        ]
        ans = 0
        for r, c in start_points:
            left, right, i, j = r, r, r, c
            while i < len_s and j < len_t:
                if s[i] != t[j]:
                    cur = i

                    # 计算 right 的位置
                    # 边界为下一个 1 出现的位置或者是到达数组长度
                    # right 即为边界的前一个位置
                    while i < len_s and j < len_t:
                        i, j = i + 1, j + 1
                        if i == len_s or j == len_t or s[i] != t[j]:
                            right = i - 1
                            break

                    dl, dr = cur - left, right - cur
                    ans += dl + dr + dl * dr + 1
                    left, cur = cur + 1, right + 1  # 更新 left, cur
                else:
                    i, j = i + 1, j + 1
        return ans

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

问题描述#

解题思路#

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