Medium

题目描述

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

比如， "computer" 和 "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 串选出来的子字符串。

示例 2：

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

约束条件：

  • 1 <= s.length, t.length <= 100
  • s 和 t 只包含小写英文字母。

解题思路

这道题需要找到两个字符串中恰好只有一个字符不同的子字符串对的数目。我们可以采用枚举的方法来解决。

主要思路是枚举所有可能的子字符串对，然后检查它们是否恰好只有一个字符不同。

方法一：暴力枚举（直接对比）

  • 枚举 s 的所有子字符串的起始位置 i
  • 枚举 t 的所有子字符串的起始位置 j
  • 枚举子字符串的长度，从位置 i 和 j 开始逐字符比较
  • 统计不同字符的个数，当恰好为 1 时，结果加一

方法二：动态规划优化（推荐）

  • 对于每个起始位置对 (i, j)，我们可以用动态规划的思想来优化
  • 预计算以每个位置为起点的相同字符的连续长度
  • 对于每个不同的字符位置，向左右扩展相同的部分

具体实现中，我们枚举每一对起始位置 (i, j)，然后从这两个位置开始比较字符。当遇到不同字符时，我们统计以这个不同字符为"唯一差异"的子字符串数量。

时间复杂度虽然看似是 O(n³)，但由于字符串长度限制为100，实际运行效率可以接受。

代码实现

class Solution {
public:
    int countSubstrings(string s, string t) {
        int m = s.length(), n = t.length();
        int result = 0;
        
        // 枚举s和t中所有可能的起始位置对
        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) {
                        result++;
                    }
                    // 如果超过一个不同字符，则后续更长的子字符串都不符合条件
                    if (diff > 1) {
                        break;
                    }
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def countSubstrings(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        result = 0
        
        # 枚举s和t中所有可能的起始位置对
        for i in range(m):
            for j in range(n):
                diff = 0
                # 从起始位置开始比较字符
                k = 0
                while i + k < m and j + k < n:
                    if s[i + k] != t[j + k]:
                        diff += 1
                    # 如果恰好有一个不同字符，则找到一个有效的子字符串对
                    if diff == 1:
                        result += 1
                    # 如果超过一个不同字符，则后续更长的子字符串都不符合条件
                    if diff > 1:
                        break
                    k += 1
        
        return result

public class Solution {
    public int CountSubstrings(string s, string t) {
        int m = s.Length, n = t.Length;
        int result = 0;
        
        // 枚举s和t中所有可能的起始位置对
        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) {
                        result++;
                    }
                    // 如果超过一个不同字符，则后续更长的子字符串都不符合条件
                    if (diff > 1) {
                        break;
                    }
                }
            }
        }
        
        return result;
    }
}

var countSubstrings = function(s, t) {
    let count = 0;
    
    for (let i = 0; i < s.length; i++) {
        for (let j = 0; j < t.length; j++) {
            let diff = 0;
            for (let k = 0; i + k < s.length && j + k < t.length; k++) {
                if (s[i + k] !== t[j + k]) {
                    diff++;
                }
                if (diff === 1) {
                    count++;
                } else if (diff > 1) {
                    break;
                }
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(m × n × min(m,n))，其中 m 和 n 分别是字符串 s 和 t 的长度。外层两重循环枚举起始位置，内层循环最多比较 min(m,n) 个字符
空间复杂度O(1)，只使用了常数级别的额外空间

相关题目