1638. Count Substrings That Differ by One Character-蒲公英云

1638. Count Substrings That Differ by One Character

梦里梦外; 2024-03-23 15:58 99阅读 0赞

Given two strings s and t, find the number of ways you can choose a non-empty substring of s and replace a single character by a different character such that the resulting substring is a substring of t. In other words, find the number of substrings in s that differ from some substring in t by exactly one character.

For example, the underlined substrings in "computer" and "computation" only differ by the 'e'/'a', so this is a valid way.

Return the number of substrings that satisfy the condition above.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "aba", t = "baba"
Output: 6
Explanation: The following are the pairs of substrings from s and t that differ by exactly 1 character:
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
The underlined portions are the substrings that are chosen from s and t.

题目：给定两个字符串s和t, 分别找s和t的子字符串subS和subT，使得将subS中一个字符替换成不同的字符可以与subT相等，简单来说就是subS和subT只差一个字符，但subS和subT的长度需要相等。问一共有多少种找法。

思路：可以用bruteforce，但用DP更简单一些。用DP就要分析题目特点：

在以下两种情况的时候可以找到新的符合要求的子字符串对：

1）如果已经找到子字符串subS1和subT1，结尾处索引分别为index_s和index_t，再继续往下比较的时候，如果s[index_s+1]与t[index_t+1]相等，则新的子字符串对符合要求；

2）如果找到完全相等的两个子字符串对subS1和subT1, 结尾处索引分别为index_s和index_t，再继续往下比较的时候，如果s[index_s+1]与t[index_t+1]不相等，则新的子字符串对符合要求；

因此，假设m = s.length(), n = t.length(), 经分析需要维护两个m*n的二维数组sameSubStrs和diffSubStrs，两个指针i和j分别指向s和t，sameSubStrs记录s中到s[i]的子字符串和t中到t[i]的子字符串完全相等的最大字符数，diffSubStrs[i][j]记录s中截止到i和t中截止到j的符合题目要求（即只有一个不同字符）的子字符串对个数，有点拗口，举个例子说一下：

数组sameSubStrs和diffSubStrs关系如下: i=2,j=2时，s[0:2] = t[0:2]，则sameSubStrs[i][j] = 3, 即s中”bac”,”ac”,”c” 和t中对应的”bac”,”ac”,”c”可以组成3个相等的子字符串对。则当i =3, j = 3时，s[i]!=t[j], diffSubStrs[i][j] = sameSubStrs[i-1][j-1] + 1. sameSubStrs[i-1][j-1]来说，构成diffSubStrs[i][j]的子字符串对分别为：”bacd”<->”bacb”, “acd”<->”acb”,”cd”<->”cb”, “d”<->”b”.

可以分析出：

当s[i] == t[j]时，sameSubStrs[i][j] = sameSubStrs[i-1][j-1] + 1

diffSubStrs[i][j] = diffSubStrs[i-1][j-1]

当s[i] != t[j]时，sameSubStrs[i][j] = 0;

diffSubStrs[i][j] = sameSubStrs[i-1][j-1] + 1

则将所有diffSubStrs[i][j]相加即为结果。

代码如下：

class Solution {
public:
    int countSubstrings(string s, string t) {
        vector<vector<int>> sameSubStrs(s.length()+1, vector<int>(t.length()+1, 0));
        vector<vector<int>> diffSubStrs = sameSubStrs;
        int res = 0;
        for(int i = 0; i < s.length(); i++){
            for(int j = 0; j < t.length(); j++){
                if(s[i] == t[j]){
                    sameSubStrs[i+1][j+1] = sameSubStrs[i][j] + 1;
                    diffSubStrs[i+1][j+1] = diffSubStrs[i][j];
                } else {
                    diffSubStrs[i+1][j+1] = sameSubStrs[i][j] + 1;
                }
                res += diffSubStrs[i+1][j+1];
            }
        }
        return res;
    }
};