中国铁道工程建设协会查证网站,上海人才网站首页,临淄信息港,南昌做网站公司题目链接 Leetcode.1638 统计只差一个字符的子串数目 Rating #xff1a; 1745 题目描述
给你两个字符串 s和 t#xff0c;请你找出 s中的非空子串的数目#xff0c;这些子串满足替换 一个不同字符 以后#xff0c;是 t串的子串。换言之#xff0c;请你找到 s和 t串中 恰…题目链接 Leetcode.1638 统计只差一个字符的子串数目 Rating 1745 题目描述
给你两个字符串 s和 t请你找出 s中的非空子串的数目这些子串满足替换 一个不同字符 以后是 t串的子串。换言之请你找到 s和 t串中 恰好 只有一个字符不同的子字符串对的数目。
比方说 computerand 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 提示
1s.length,t.length1001 s.length, t.length 1001s.length,t.length100s和 t都只包含小写英文字母。
解法dp
对于 s我们可以考虑每次以 s[i](0≤in)(0 \leq i n)(0≤in)开始的 s的子串s和 t进行匹配。
当 s与t进行匹配时不同字符数量为 d。当 d 1时答案 1。当 d 1时退出循环接着匹配以 s[i1]为起点的子串。
时间复杂度O(m∗n∗min(m,n))O(m*n*min(m,n))O(m∗n∗min(m,n))
C代码
class Solution {
public: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 d 0;for(int k 0;i k m j k n;k){d (s[i k] ! t[j k]);if(d 1) break;if(d 1) ans;}}}return ans;}
};
Python代码
class Solution:def countSubstrings(self, s: str, t: str) - int:m , n len(s) , len(t)ans 0for i in range(m):for j in range(n):d , k 0 , 0while i k m and j k n:d d (1 if s[i k] ! t[j k] else 0)if d 1:breakif d 1:ans ans 1k k 1return ans
