Java编程实战9：统计只差一个字符的子串数目

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

题目

给你两个字符串 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 都只包含小写英文字母。

解题思路

二重遍历字符串 s 和 t ； 对于字符串中的字符 s[i] 与 t[j] ，如果二者相等，那么 continue ； 当二者不等，分别以 s[i] 与 t[j] 为中心同步向左或向右扩散，扩散条件是二者的左/右字符相同，每扩散一次表示答案加一；
下图展示了一个中心扩散的例子，其中 s = “aabab”, t = “aacac”, i = j = 2 ： 中心扩散例子

如图所示，上述情形中一共贡献了6种不同的满足条件的答案。
容易得到，当 s[i] 与 t[j] 不同时， (i, j) 贡献的答案数为：(1+end_{ij})*(1+start_{ij}) 其中end_{ij}表示以s[i-1]与t[j-1]为终点的最长相同后缀的长度，start_{ij}表示以 s[i+1] 与 t[j+1] 为起点的最长相同前缀的长度。（即C_{end_{ij}+1}^{1*C_{start_{ij}+1}}1，选择差一字符串的起点和终点）
如上例中，对于 s[2]为b 和 t[2]为c ，其左侧最长后缀为 aa 长度为2，右侧最长后缀为 a 长度为1， 所以 i=2, j=2 这种情况一共贡献了：(1+2)*(1+1) = 6种答案。

完整代码

class Solution {
    public int countSubstrings(String s, String t) {
        char[] cs = s.toCharArray();
        char[] ct = t.toCharArray();
        int count = 0;
        // start[i][j] 表示 以s[i]与t[j]开头，相同的字符串长度
        int[][] start = new int[cs.length][ct.length];
        for (int i = cs.length - 1; i >= 0; i--) {
            for (int j = ct.length - 1; j >= 0; j--) {
                if (cs[i] != ct[j]) continue;
                start[i][j] = i == cs.length - 1 || j == ct.length - 1 ? 1 : start[i + 1][j + 1] + 1;
            }
        }
        // end[i][j] 表示 以s[i]与t[j]结尾，相同的字符串长度
        int[][] end = new int[cs.length][ct.length];
        for (int i = 0; i < cs.length; i++) {
            for (int j = 0; j < ct.length; j++) {
                if (cs[i] != ct[j]) continue;
                end[i][j] = i == 0 || j == 0 ? 1 : end[i - 1][j - 1] + 1;
            }
        }
        for (int i = 0; i < cs.length; i++) {
            for (int j = 0; j < ct.length; j++) {
                if (cs[i] == ct[j]) continue;
                int left = i > 0 && j > 0 ? end[i - 1][j - 1] : 0;
                int right = i < cs.length - 1 && j < ct.length - 1 ? start[i + 1][j + 1] : 0;
                count += (left + 1) * (right + 1);
            }
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32