2023-03-27 LeetCode：1638. 统计只差一个

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

问题描述

给你两个字符串 s 和 t ，请你找出 s 中的非空子串的数目，这些子串满足替换 一个不同字符 以后，是 t 串的子串。换言之，请你找到 s 和 t 串中 恰好 只有一个字符不同的子字符串对的数目。
比方说， computer and computation 只有一个字符不同： e/a ，所以这一对子字符串会给答案加 1 。
请你返回满足上述条件的不同子字符串对数目。
一个 子字符串 是一个字符串中连续的字符。

示例

输入：s = "aba", t = "baba"
输出：6
解释：以下为只相差 1 个字符的 s 和 t 串的子字符串对：
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
加粗部分分别表示 s 和 t 串选出来的子字符串。

输入：s = "ab", t = "bb"
输出：3
解释：以下为只相差 1 个字符的 s 和 t 串的子字符串对：
("ab", "bb")
("ab", "bb")
("ab", "bb")
加粗部分分别表示 s 和 t 串选出来的子字符串。

解题思路

核心思路：暴力枚举、动态规划

1. 暴力枚举

枚举s字串的起始位置，再枚举t字串的起始位置，然后枚举字符串的长度，如果不同为1，结果res++；如果不同大于1，结束字符串长度的枚举。

2. 问题优化+动态规划

问题优化
不用暴力求解的方法，我们可以设想一下可以如何从字符串 s 和 t中得到只有1位不同的子字符串对？
我们可以这样：假如字符串 s 和 t中的s[i]和t[j]是不同的字符，只要满足s[i-1]=t[j-1]或s[i+1]=t[j+1]，那么我们可以根据这个字符的位置向左、向右延伸获取到更长的满足条件的字符串。

如果最长可以获取如图所示的字符串，我们可以算出以s[i]和t[j]为不同字符的所有满足条件的字符串数量：(left+1) * (right+1)；只要我们将所有不同的字符对按照这个逻辑计算并求和，就能得出结果。
因此，我们的问题就变成了求所有不同的字符对在左、右连续相等的长度。
动态规划
假设dpl[i][j]表示左边到当前位置连续相等的字符串长度，dpr[i][j]表示右边到当前位置连续相等的字符串长度，我们可以用动态规划进行递推：
求dpl:
如果s[i]!=t[j]，dpl[i, j] = 0
如果s[i]=t[j]，dpl[i, j] = dpl[i - 1, j - 1] + 1
求dpr:
如果s[i]!=t[j]，dpr[i, j] = 0;
如果s[i]=t[j]，dpr[i, j] = dpr[i + 1, j + 1] + 1.

代码示例（JAVA）

1. 暴力枚举

class Solution {
    public int countSubstrings(String s, String t) {
        int res = 0, m = s.length(), n = t.length();
        // 枚举s字串的起始位置
        for (int i = 0; i < m; i++) {
            //  枚举t字串的起始位置
            for (int j = 0; j < n; j++) {
                int count = 0;
                // 枚举长度
                for (int k = 0; k < m - i && k < n - j; k++) {
                    if (s.charAt(i + k) != t.charAt(j + k)) {
                        count++;
                    }
                    // 不同为1，结果加1
                    if (count == 1) {
                        res++;
                    } else if (count > 1) {
                        break;
                    }
                }
            }
        }
        
        return res; 
    }
}

时间复杂度：O(n*m*min(n,m))

2. 动态规划

class Solution {
    public int countSubstrings(String s, String t) {
        int res = 0, m = s.length(), n = t.length();
        int[][] dpl = new int[m][n];
        int[][] dpr = new int[m][n];
        // 求dpl
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (s.charAt(i) == t.charAt(j)) {
                    dpl[i][j] = (i - 1 >= 0 && j - 1 >= 0 ? dpl[i - 1][j - 1] : 0) + 1;
                } else {
                    dpl[i][j] = 0;
                }
            }
        }
        // 求dpr
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (s.charAt(i) == t.charAt(j)) {
                    dpr[i][j] = (i + 1 < m && j + 1 < n ? dpr[i + 1][j + 1] : 0) + 1;
                } else {
                    dpr[i][j] = 0;
                }
            }
        }

        // 求总和
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (s.charAt(i) != t.charAt(j)) {
                    int left = i - 1 >= 0 && j - 1 >= 0 ? dpl[i - 1][j - 1] : 0;
                    int right = i + 1 < m && j + 1 < n ? dpr[i + 1][j + 1] : 0;
                    res += (left + 1) * (right + 1);
                }
            }
        }

        return res;
    }
}

时间复杂度：O(n*m)