1638. Count Substrings That Differ by One Character

梦里梦外; 2024-03-23 15:58 35阅读 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的符合题目要求（即只有一个不同字符）的子字符串对个数，有点拗口，举个例子说一下：

![3511de5d85164f5aa7727eb76f62015e.png][]

数组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;
        }
    };

[3511de5d85164f5aa7727eb76f62015e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/c1a270efdb01413ebe118d203945e669.png

发表评论取消回复

表情：

评论列表（有 0 条评论，35人围观）

还没有评论，来说两句吧...

相关阅读

相关 1638. Count Substrings That Differ by One Character

Given two strings `s` and `t`, find the number of ways you can choose a non-empty substr

梦里梦外;/ 2024年03月23日 15:58/ 0 赞/ 36 阅读

相关 Count Substrings That Differ by One Character（C++统计只差一个字符的子串数目）

解题思路：（1）计算s的所有子字符串，并与t匹配 class Solution { public: int helper

约定不等于承诺〃/ 2023年01月06日 04:28/ 0 赞/ 129 阅读

相关 Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. F

- 日理万妓/ 2022年08月20日 05:09/ 0 赞/ 14 阅读

相关 Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters Given a string, find the length of the

快来打我*/ 2022年08月06日 10:18/ 0 赞/ 126 阅读

相关 the difference between substr and substrb

实例分析： select substrb('大小abc',1,2) from dual; --大 select lengthb(substrb('大小abc',1,2)

电玩女神/ 2022年07月10日 04:03/ 0 赞/ 344 阅读

相关 Longest Substring Without Repeating Characters

题目 Given a string, find the length of the longest substring without repeating char

短命女/ 2022年06月08日 11:46/ 0 赞/ 188 阅读

相关 Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

冷不防/ 2022年06月08日 08:13/ 0 赞/ 123 阅读

相关 696.Count Binary Substrings

> Give a string s, count the number of non-empty (contiguous) substrings > that have t

约定不等于承诺〃/ 2022年05月30日 06:38/ 0 赞/ 127 阅读

相关 substr_count() 函数

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlbmd5

傷城~/ 2022年03月15日 15:58/ 0 赞/ 232 阅读

相关 Longest Substring Without Repeating Characters

题意为给出一个字符串，找出其中没有重复字符的最长子序列的长度。brute force的复杂度为O(n^3).依次查找每个子字符串是否含有重复字符，并比较长度。开始看到题目，想用

淡淡的烟草味﹌/ 2021年12月17日 10:27/ 0 赞/ 139 阅读