LeetCode | 1638.统计只差一个字符的子串数目
给你两个字符串 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 都只包含小写英文字母。
思路：
方案一：枚举
脑海里的第一个想到的就是枚举，
最开始的想法：
先枚举所有长度为 1 的子串，看有多少满足条件；
再枚举所有长度为 2 的子串，看有多少满足条件；
...
直到枚举完长度为 min(s.size(), t.size()) 的子串
这种方案有个问题，每次判断是否满足 只有一个字符不同 的条件时，都要遍历完整个子串，很浪费时间。
于是采用另一种枚举方案：
先枚举从下标 0 开始的所有子串，看有多少满足条件；
先枚举从下标 1 开始的所有子串，看有多少满足条件；
...
直到枚举完从下标为 min(s.size() - 1, t.size() - 1) 开始的所有子串
这种方案的好处是：每一轮开始的下标是固定的，可以记录下之前有多少个字符串不同，在判断是否满足条件时，不用每次重新遍历整个子串。
设 diff 为从起点开始到当前位置有多少个不同字符（起点是从哪个下标开始遍历子串：0、1、2 ...）
在遍历到第 k 个子串时：
- 如果 s[i + k] == t[j + k], 此时 diff 不变
- 如果 s[i + k] != t[j + k], 此时 diff += 1;
- 如果 diff == 0, 继续往后遍历
- 如果 diff == 1, ans++
- 如果 diff > 1, 停止遍历当前起点开始的子串
int countSubstrings(string s, string t) {
int m = s.size(), n = t.size();
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int diff = 0;
for (int k = 0; i + k < m && j + k < n; k++) {
if (s[i + k] != t[j + k]) {
++diff;
}
if (diff == 1) {
++ans;
} else if (diff > 1) {
break;
}
}
}
}
return ans;
}
时间复杂度 O(m * n * min(m, n))
方案二：动态规划
题目是找出 只有一个字符不同 的子串，可以遍历两个字符串，求当 s[i] != t[j] 时, 以 s[i] 和 t[j] 做为不同字符的子串一共有多少个。
以s[i] 和 t[j] 做为不同字符时，s[i] 和 t[j] 左右两边的字符一定是相同的
设 s[i] 和 t[j] 左边有 m 个相同的字符, 右边有 n 个相同的字符；则 s[i] 和 t[j] 做为不同字符的字符串一共有 (m + 1) * (n + 1) 个。（左右两边的子串做组合，左右两边的字符串可以为空，多了一种可能性, 所以要加 1）
s[i] 和 t[j] 左右两边相同的字符数量可以通过动态规划求得
int countSubstrings(string s, string t) {
int m = s.size(), n = t.size();
vector<vector<int>> dpl(m, vector<int>(n));
vector<vector<int>> dpr(m, vector<int>(n));
for (int i = 0; i < m - 1; i++) {
for (int j = 0; j < n - 1; j++) {
dpl[i + 1][j + 1] = s[i] == t[j] ? dpl[i][j] + 1 : 0;
}
}
for (int i = m - 1; i > 0; i--) {
for (int j = n - 1; j > 0; j--) {
dpr[i - 1][j - 1] = s[i] == t[j] ? dpr[i][j] + 1 : 0;
}
}
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (s[i] != t[j]) {
ans += (dpl[i][j] + 1) * (dpr[i][j] + 1);
}
}
}
return ans;
}
时间复杂度O(m * n)