Luobuyu's Blog

0%

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

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 1.1k 阅读时长 ≈ 1 分钟
类似最长公共子序列问题，注意下标技巧。

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

题目描述：

给出两个字符串 $ s,t $ ，找出 $ s $ 中的非空子串的数目，这些子串满足替换一个不同字符之后，是 $ t $ 串的子串。请找出 $ s $ 和 $ t $ 串中恰好只有一个字符不同的子字符串对的数目。

数据范围：
$ 1\le s.length,t.length\le 100 $

题解：

数据范围很小可以直接暴力。也可以使用动态规划做。

类似最长公共子序列问题，可以使用 $ dp[i][j][0/1] $ 表示以 $ s[i] $ 和 $ t[j] $ 为终点的长度相同的相同字符串或只有一个不同的字符串的个数。那么可以得到递推方程

$ s[i] = s[j] $ 时， $ dp[i-1][j-1][0] $ 表示之前的完全相同的字符串延长一个字符， $ +1 $ 表示，单独的 $ s[i],s[j] $ 也是一个新的完全相同的子串。同理可以得到另外两个方程。

因为给出的字符串下标从 $ 0 $ 开始，所以其实按照上面的方程不太好实现代码。这里有一个技巧，可以用 $ i + 1 $ 替代 $ i $ ， $ j + 1 $ 替换 $ j $ ，实际上得到的递推数组下标从 $ 1 $ 开始。

也可以直接假定下标为 $ 1 $ ，那么只需要在 $ s[i],s[j] $ 判断的时候取真实下标即可。

代码：

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
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const static int INF = 0x3f3f3f3f;
    int dp[101][101][2];
    int countSubstrings(string s, string t)
    {
        int m = s.length(), n = t.length();
        int ans = 0;
        for (int i = 1; i <= m; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                if (s[i - 1] == t[j - 1])
                {
                    dp[i][j][0] = dp[i - 1][j - 1][0] + 1;
                    dp[i][j][1] = dp[i - 1][j - 1][1];
                }
                else
                {
                    dp[i][j][1] = dp[i - 1][j - 1][0] + 1;
                }
                ans += dp[i][j][1];
            }
        }
        return ans;
    }
};