题目:给你两个字符串 s 和 t ,请你找出 s 中的非空子串的数目,这些子串满足替换一个不同字符以后,是 t 串的子串。换言之,请你找到 s 和 t 串中 恰好 只有一个字符不同的子字符串对的数目
我们的思路是,定义两个指针,一个为s子串的起点,一个为t子串的起点,然后定义一个指针k为s和t子串的长度,遍历k的位置然后比较长度为k的子串是否满足题目要求;
下面我们看代码以及注释:
int countSubstrings(char* s, char* t)
{
//先计算s和t的长度
int lens = strlen(s);
int lent = strlen(t);
//count统计符合题要的答案
int count = 0;
//给定i的起点
for (int i = 0; i < lens; i++)
{
//给定j的起点
for (int j = 0; j < lent; j++)
{
//flag用来记录当前这个符合要求的字符串,当他还是符合题意的时候会是1,count也会++
//当它再次遇到下一个不同的字符的时候,会变成2,那就结束当前的字符串,这个字符串就是符合题意的子字符串
//每次结束当前字符串的时候flag要重新置为0,继续寻找符合题意的下一个子字符串
int flag = 0;
//给定k的起点
for (int k = 0; i + k < lens && j + k < lent; k++)
{
//符合只有一个字符不同的时候flag++
if (s[i + k] != t[j + k])
{
flag++;
}
//当这个子字符串有两个字符不同时不满足题意,退出当前子字符串的遍历
if (flag > 1)
{
break;
}
else if (flag == 1)
{
count++;
}
}
}
}
return count;
}
int main()
{
char s[] = "aba";
char t[] = "baba";
int ret = countSubstrings(s, t);
printf("%d\n", ret);
return 0;
}