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 都只包含小写英文字母。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-substrings-that-differ-by-one-character
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

可以暴力枚举子串和子串的开始下标，然后各自往后遍历，找到只差一位时停止。时间复杂度为)#card=math&code=O%28m%2An%2Amin%28m%2Cn%29%29&id=IMJmL)。

考虑对暴力方法进行优化，我们枚举子串的结束下标，涉及连续子串一般都可以考虑“以当前位置结束”，从而使用动态规划。

记表示和分别以和结尾的满足条件的子串对数，那可以从什么状态转移过来呢？

当时，可以想到有。

当时，因为这两个字符不相同，所以前面的字符必须都相同了，前面相同的长度加一就是满足条件的对数。那么需要求和的最长公共后缀的长度，记为，那么有。最后返回的答案就是所有的和。

这道题目可以学到很多东西，从暴力到DP，再到DP的空间也可以优化，具体细节见代码注释。

代码

暴力 )#card=math&code=O%28m%2An%2Amin%28m%2Cn%29%29&id=GavcE)

class Solution {
    public int countSubstrings(String s, String t) {
        int n = s.length();
        int m = t.length();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                int diff = 0;
                for (int k = 0; i + k < n && j + k < m; ++k) {
                    if (s.charAt(i + k) != t.charAt(j + k)) {
                        diff++;
                    }
                    if (diff > 1) {
                        break;
                    }
                    if (diff == 1) {
                        ans++;
                    }
                }
            }
        }
        return ans;
    }
}

二维DP #card=math&code=O%28m%2An%29&id=TNBsO)

class Solution {
    public int countSubstrings(String s, String t) {
        int n = s.length();
        int m = t.length();
        // g[i][j]表示s[0,i]和t[0,j]的最长公共后缀的长度
        // 声明的矩阵大小行和列都增加1，省去了边界讨论，下面f同理
        int[][] g = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                g[i][j] = s.charAt(i - 1) == t.charAt(j - 1) ? g[i - 1][j - 1] + 1 : 0;
            }
        }
        int ans = 0;
        // f[i][j]表示s和t分别以s[i]和t[j]结尾的满足条件的子串对数
        int[][] f = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                f[i][j] = s.charAt(i - 1) == t.charAt(j - 1) ? f[i - 1][j - 1] : g[i - 1][j - 1] + 1;
                ans += f[i][j];
            }
        }
        return ans;
    }
}

注意到上面代码的两个for循环可以合并，得到如下代码

class Solution {
    public int countSubstrings(String s, String t) {
        int n = s.length();
        int m = t.length();
        int ans = 0;
        int[][] g = new int[n + 1][m + 1];
        int[][] f = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                g[i][j] = s.charAt(i - 1) == t.charAt(j - 1) ? g[i - 1][j - 1] + 1 : 0;
                f[i][j] = s.charAt(i - 1) == t.charAt(j - 1) ? f[i - 1][j - 1] : g[i - 1][j - 1] + 1;
                ans += f[i][j];
            }
        }
        return ans;
    }
}

DP O(1)空间

观察以上DP代码，发现和都只和左上角的值有关。因此如果按对角线遍历矩阵，只需要维护两个变量即可，而不需要真实地开辟矩阵空间。

下面遍历矩阵对角线的写法参考「零神」的代码。真的优雅，需要牢记。

class Solution {
    public int countSubstrings(String s, String t) {
        int n = s.length();
        int m = t.length();
        int ans = 0;
        // 从右上角开始，按对角线方向进行遍历
        for (int delta = -(m - 1); delta <= n - 1; delta++) {
            int i = 0;
            int j = 0;
            // delta为负表示列，为正表示行
            if (delta < 0) {
                j = -delta;
            } else {
                i = delta;
            }
            int g = 0;
            int f = 0;
            for (; i < n && j < m; ++i, ++j) {
                // 这里f的值依赖g，因此需要先更新f再更新g
                f = s.charAt(i) == t.charAt(j) ? f : g + 1;
                g = s.charAt(i) == t.charAt(j) ? g + 1 : 0;
                ans += f;
            }
        }
        return ans;
    }
}