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

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

比方说, "computer" and "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 都只包含小写英文字母。

思路:
方案一:枚举
 脑海里的第一个想到的就是枚举,
 最开始的想法:
  先枚举所有长度为 1 的子串,看有多少满足条件;
  再枚举所有长度为 2 的子串,看有多少满足条件;
  ...
  直到枚举完长度为 min(s.size(), t.size()) 的子串
  这种方案有个问题,每次判断是否满足 只有一个字符不同 的条件时,都要遍历完整个子串,很浪费时间。

 于是采用另一种枚举方案:
  先枚举从下标 0 开始的所有子串,看有多少满足条件;
  先枚举从下标 1 开始的所有子串,看有多少满足条件;
  ...
  直到枚举完从下标为 min(s.size() - 1, t.size() - 1) 开始的所有子串
  这种方案的好处是:每一轮开始的下标是固定的,可以记录下之前有多少个字符串不同,在判断是否满足条件时,不用每次重新遍历整个子串。

 设 diff 为从起点开始到当前位置有多少个不同字符(起点是从哪个下标开始遍历子串:0、1、2 ...)
 在遍历到第 k 个子串时:

  • 如果 s[i + k] == t[j + k], 此时 diff 不变
  • 如果 s[i + k] != t[j + k], 此时 diff += 1;
  • 如果 diff == 0, 继续往后遍历
  • 如果 diff == 1, ans++
  • 如果 diff > 1, 停止遍历当前起点开始的子串
int countSubstrings(string s, string t) {
    int m = s.size(), n = t.size();
    int ans = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int diff = 0;
            for (int k = 0; i + k < m && j + k < n; k++) {
                if (s[i + k] != t[j + k]) {
                    ++diff;
                }
                if (diff == 1) {
                    ++ans;
                } else if (diff > 1) {
                    break;
                }
            }
        }
    }
    return ans;
}

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

方案二:动态规划
 题目是找出 只有一个字符不同 的子串,可以遍历两个字符串,求当 s[i] != t[j] 时, 以 s[i] 和 t[j] 做为不同字符的子串一共有多少个。

 以s[i] 和 t[j] 做为不同字符时,s[i] 和 t[j] 左右两边的字符一定是相同的

 设 s[i] 和 t[j] 左边有 m 个相同的字符, 右边有 n 个相同的字符;则 s[i] 和 t[j] 做为不同字符的字符串一共有 (m + 1) * (n + 1) 个。(左右两边的子串做组合,左右两边的字符串可以为空,多了一种可能性, 所以要加 1)

 s[i] 和 t[j] 左右两边相同的字符数量可以通过动态规划求得

int countSubstrings(string s, string t) {
    int m = s.size(), n = t.size();
    vector<vector<int>> dpl(m, vector<int>(n));
    vector<vector<int>> dpr(m, vector<int>(n));
    for (int i = 0; i < m - 1; i++) {
        for (int j = 0; j < n - 1; j++) {
            dpl[i + 1][j + 1] = s[i] == t[j] ? dpl[i][j] + 1 : 0;
        }
    }
    for (int i = m - 1; i > 0; i--) {
        for (int j = n - 1; j > 0; j--) {
            dpr[i - 1][j - 1] = s[i] == t[j] ? dpr[i][j] + 1 : 0;
        }
    }
    int ans = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (s[i] != t[j]) {
                ans += (dpl[i][j] + 1) * (dpr[i][j] + 1);
            }
        }
    }
    return ans;
}

时间复杂度O(m * n)

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇