class Solution {
public:
int countSubstrings(string s, string t) {
}
};
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 <= 100s 和 t 都只包含小写英文字母。原站题解
python3 解法, 执行用时: 60 ms, 内存消耗: 14.9 MB, 提交时间: 2022-11-17 18:00:51
class Solution:
def countSubstrings(self, s: str, t: str) -> int:
m, n = len(s), len(t)
# 方法二：只存储斜上方的值
# 记录 (以s[i]和t[j]结尾的 满足条件的子字符串对数目, 连续相同的位数)
tot = 0
# 左下角
for i in range(m-1, -1, -1):
last = (0, 0) # 初始
for j in range(min(m-i, n)):
if s[i+j] == t[j]:
cur = (last[0], last[1] + 1)
tot += last[0]
else:
cur = (last[1] + 1, 0)
tot += last[1] + 1
last = cur
# 补全右上角
for j in range(1, n):
last = (0, 0)
for i in range(min(n-j, m)):
if s[i] == t[j+i]:
cur = (last[0], last[1] + 1)
tot += last[0]
else:
cur = (last[1] + 1, 0)
tot += last[1] + 1
last = cur
return tot
python3 解法, 执行用时: 68 ms, 内存消耗: 14.9 MB, 提交时间: 2022-11-17 18:00:31
class Solution:
def countSubstrings(self, s: str, t: str) -> int:
m, n = len(s), len(t)
# 方法一：用dp存储一行
dp = [(0, 0)]*(n+1) # 记录 (以s[i]和t[j]结尾的 满足条件的子字符串对数目, 连续相同的位数)
tot = 0 # 总的满足条件的子字符串对数目
for i in range(m):
last = dp[0]
for j in range(n):
if s[i] == t[j]:
cur = (dp[j][0], dp[j][1] + 1)
tot += dp[j][0]
else:
cur = (dp[j][1] + 1, 0)
tot += dp[j][1] + 1
dp[j], last = last, cur
dp[n] = last
return tot