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

链接：1638.统计只差一个字符的子串数目
难度：Medium
标签：哈希表、字符串、动态规划、枚举
简介：给你两个字符串 s 和 t ，请你找出 s 中的非空子串的数目，这些子串满足替换 一个不同字符 以后，是 t 串的子串。换言之，请你找到 s 和 t 串中 恰好 只有一个字符不同的子字符串对的数目。

题解 1 - cpp

• 编辑时间：2023-03-27
• 执行用时：4ms
• 内存消耗：6.1MB
• 编程语言：cpp
• 解法介绍：枚举。

class Solution {
public:
    int countSubstrings(string s, string t) {
        int n = s.size(), m = t.size(), res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int cnt = 0;
                for (int k = 0; i + k < n && j + k < m; k++) {
                    if (s[i + k] != t[j + k]) cnt++;
                    if (cnt == 1) res++;
                    else if (cnt > 1) break;
                }
            }
        }
        return res;
    }
};

题解 2 - python

• 编辑时间：2023-03-27
• 执行用时：72ms
• 内存消耗：14.7MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def countSubstrings(self, s: str, t: str) -> int:
        n, m, res = len(s), len(t), 0
        for i in range(n):
            for j in range(m):
                cnt, k = 0, 0
                while i+k < n and j+k < m:
                    if s[i+k] != t[j+k]:
                        cnt += 1
                    if cnt == 1:
                        res += 1
                    elif cnt > 1:
                        break
                    k += 1
        return res

题解 3 - rust

• 编辑时间：2023-03-27
• 内存消耗：2MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn count_substrings(s: String, t: String) -> i32 {
        let (s, t) = (
            s.chars().collect::<Vec<char>>(),
            t.chars().collect::<Vec<char>>(),
        );
        let (n, m, mut res) = (s.len(), t.len(), 0);
        for i in 0..n {
            for j in 0..m {
                let (mut cnt, mut k) = (0, 0);
                while i + k < n && j + k < m {
                    if s[i + k] != t[j + k] {
                        cnt += 1
                    }
                    if cnt == 1 {
                        res += 1
                    } else if cnt > 1 {
                        break;
                    }
                    k += 1
                }
            }
        }
        res
    }
}