题目
给你两个字符串 s
和 t
,请找出 s
中的非空子串的数目,这些子串满足替换一个不同字符以后,是 t
串的子串。换言之,请你找到 s
和 t
串中恰好只有一个字符不同的子字符串对的数目。
一个子字符串是一个字符串中连续的字符。
示例
示例 1
输入:
s = "aba", t = "baba"
输出:
6
解释:
以下为只相差 1 个字符的 s
和 t
串的子字符串对:
- (“aba”, “baba”)
- (“aba”, “baba”)
- (“aba”, “baba”)
- (“aba”, “baba”)
- (“aba”, “baba”)
- (“aba”, “baba”)
示例 2
输入:
s = "ab", t = "bb"
输出:
3
解释:
以下为只相差 1 个字符的 s
和 t
串的子字符串对:
- (“ab”, “bb”)
- (“ab”, “bb”)
- (“ab”, “bb”)
示例 3
输入:
s = "a", t = "a"
输出:
0
示例 4
输入:
s = "abe", t = "bbc"
输出:
10
提示
- 1 <=
s.length, t.length
<= 100 s
和t
都只包含小写英文字母。
代码
#include <string.h>
#include <stdbool.h>
#include <stdio.h>
bool isOnlyOneDiff(const char* a,const char* b,int len)
{
// printf("input %s,%s\n",a,b);
int diffcnt = 0;
for (int i = 0; i < len; i++)
{
// printf("compare [%c, %c]\n",a[i], b[i]);
if(a[i] == b[i])
{
continue;
}
diffcnt++;
if(diffcnt > 1)
{
return false;
}
}
return (diffcnt == 1);
}
int countSubstrings(char* s, char* t) {
int len_s = strlen(s);
int len_t = strlen(t);
int res = 0;
int smallerLen = (len_s <= len_t) ? len_s : len_t;
int biggerLen = (len_s > len_t) ? len_s : len_t;
char* smallerStr = (len_s <= len_t) ? s : t;
char* biggerStr = (len_s > len_t) ? s : t;
// 满足题目呀求的子串长度一定相同,因此按照长度来遍历
for (int l = 0; l < smallerLen; l++)
{
char* small = smallerStr;
char* big = biggerStr;
while (small + l * sizeof(char) < smallerStr + smallerLen * sizeof(char))
{
// printf("small while\n");
while (big + l * sizeof(char) < biggerStr + biggerLen * sizeof(char))
{
// printf("big while\n");
if(isOnlyOneDiff(small,big,l+1))
{
// printf("true\n");
res++;
}
big += sizeof(char);
}
big = biggerStr;
small += sizeof(char);
}
}
return res;
}
// int main(void)
// {
// char a[] = "ab";
// char b[] = "bb";
// int res = countSubstrings(a,b);
// printf("res = %d\n",res);
// }
解法思路
- 遍历
s
中的所有子串。 - 遍历
t
中的所有子串。 - 比较
s
的子串和t
的子串,检查它们是否只有一个字符不同。 - 统计满足条件的子字符串对的数量。
代码思路分析
这个程序的目标是找出字符串 s
中的非空子串的数目,这些子串替换一个字符以后,可以成为字符串 t
的子串。具体思路如下:
-
函数
isOnlyOneDiff
:- 检查两个相同长度的子串是否只有一个字符不同。
- 计数不同字符的数量,如果超过一个,返回
false
。
-
函数
countSubstrings
:- 获取字符串
s
和t
的长度。 - 判断
s
和t
中较短的那个字符串,并设定为smallerStr
,另一个为biggerStr
。 - 通过双重循环,遍历所有可能的子串组合,并利用
isOnlyOneDiff
检查每对子串是否只有一个字符不同。 - 统计满足条件的子串对数目。
- 获取字符串
分块拆解分析
1. isOnlyOneDiff
函数
bool isOnlyOneDiff(const char* a, const char* b, int len) {
int diffcnt = 0;
for (int i = 0; i < len; i++) {
if (a[i] != b[i]) {
diffcnt++;
if (diffcnt > 1) {
return false;
}
}
}
return (diffcnt == 1);
}
- 输入:两个字符串子串
a
和b
及其长度len
。 - 输出:
true
或false
,表示两个子串是否仅有一个字符不同。 - 逻辑:遍历子串,计数不同字符数量,若超过一个字符不同则返回
false
,否则返回是否恰好有一个字符不同。
2. countSubstrings
函数
int countSubstrings(char* s, char* t) {
int len_s = strlen(s);
int len_t = strlen(t);
int res = 0;
int smallerLen = (len_s <= len_t) ? len_s : len_t;
int biggerLen = (len_s > len_t) ? len_s : len_t;
char* smallerStr = (len_s <= len_t) ? s : t;
char* biggerStr = (len_s > len_t) ? s : t;
for (int l = 0; l < smallerLen; l++) {
char* small = smallerStr;
char* big = biggerStr;
while (small + l * sizeof(char) < smallerStr + smallerLen * sizeof(char)) {
while (big + l * sizeof(char) < biggerStr + biggerLen * sizeof(char)) {
if (isOnlyOneDiff(small, big, l + 1)) {
res++;
}
big += sizeof(char);
}
big = biggerStr;
small += sizeof(char);
}
}
return res;
}
- 输入:两个字符串
s
和t
。 - 输出:满足条件的子字符串对的数量
res
。 - 逻辑:
- 获取字符串长度。
- 确定较短的字符串为
smallerStr
,较长的为biggerStr
。 - 通过双重循环遍历所有可能的子串组合。
- 使用
isOnlyOneDiff
函数检查每对子串是否只有一个字符不同,并统计满足条件的对子数量。
复杂度分析
时间复杂度
-
isOnlyOneDiff
函数:- 时间复杂度为
O(l)
,其中l
是子串的长度。
- 时间复杂度为
-
countSubstrings
函数:- 外层循环遍历子串长度,最多为
O(n)
次,其中n
是较短字符串的长度。 - 内层双重循环分别遍历
smallerStr
和biggerStr
的子串,每次遍历进行isOnlyOneDiff
检查。 - 综上,时间复杂度为
O(n^3)
,因为对于每个可能的子串长度l
,内层循环总共最多执行O(n^2)
次,每次比较需要O(l)
时间。
- 外层循环遍历子串长度,最多为
空间复杂度
- 主要使用了若干指针变量和计数变量,额外空间复杂度为
O(1)
。
结果
总结
通过遍历所有可能的子串组合,并利用辅助函数检查每对子串是否只有一个字符不同,最终统计满足条件的对子数量。算法时间复杂度较高为 O(n^3)
,但对于题目限定的字符串长度范围(<= 100)是可以接受的。