首页 > 其他分享 >1638. 统计只差一个字符的子串数目

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

时间:2024-06-03 15:00:52浏览次数:24  
标签:子串 1638 len char int 只差 字符串 sizeof

题目

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

一个子字符串是一个字符串中连续的字符。

示例

示例 1

输入
s = "aba", t = "baba"

输出
6

解释
以下为只相差 1 个字符的 st 串的子字符串对:

  1. (“aba”, “baba”)
  2. (“aba”, “baba”)
  3. (“aba”, “baba”)
  4. (“aba”, “baba”)
  5. (“aba”, “baba”)
  6. (“aba”, “baba”)

示例 2

输入
s = "ab", t = "bb"

输出
3

解释
以下为只相差 1 个字符的 st 串的子字符串对:

  1. (“ab”, “bb”)
  2. (“ab”, “bb”)
  3. (“ab”, “bb”)

示例 3

输入
s = "a", t = "a"

输出
0

示例 4

输入
s = "abe", t = "bbc"

输出
10

提示

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

代码

#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);
// }

解法思路

  1. 遍历 s 中的所有子串。
  2. 遍历 t 中的所有子串。
  3. 比较 s 的子串和 t 的子串,检查它们是否只有一个字符不同。
  4. 统计满足条件的子字符串对的数量。

代码思路分析

这个程序的目标是找出字符串 s 中的非空子串的数目,这些子串替换一个字符以后,可以成为字符串 t 的子串。具体思路如下:

  1. 函数 isOnlyOneDiff

    • 检查两个相同长度的子串是否只有一个字符不同。
    • 计数不同字符的数量,如果超过一个,返回 false
  2. 函数 countSubstrings

    • 获取字符串 st 的长度。
    • 判断 st 中较短的那个字符串,并设定为 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);
}
  • 输入:两个字符串子串 ab 及其长度 len
  • 输出truefalse,表示两个子串是否仅有一个字符不同。
  • 逻辑:遍历子串,计数不同字符数量,若超过一个字符不同则返回 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;
}
  • 输入:两个字符串 st
  • 输出:满足条件的子字符串对的数量 res
  • 逻辑
    1. 获取字符串长度。
    2. 确定较短的字符串为 smallerStr,较长的为 biggerStr
    3. 通过双重循环遍历所有可能的子串组合。
    4. 使用 isOnlyOneDiff 函数检查每对子串是否只有一个字符不同,并统计满足条件的对子数量。

复杂度分析

时间复杂度

  • isOnlyOneDiff 函数

    • 时间复杂度为 O(l),其中 l 是子串的长度。
  • countSubstrings 函数

    • 外层循环遍历子串长度,最多为 O(n) 次,其中 n 是较短字符串的长度。
    • 内层双重循环分别遍历 smallerStrbiggerStr 的子串,每次遍历进行 isOnlyOneDiff 检查。
    • 综上,时间复杂度为 O(n^3),因为对于每个可能的子串长度 l,内层循环总共最多执行 O(n^2) 次,每次比较需要 O(l) 时间。

空间复杂度

  • 主要使用了若干指针变量和计数变量,额外空间复杂度为 O(1)

结果

结果

总结

通过遍历所有可能的子串组合,并利用辅助函数检查每对子串是否只有一个字符不同,最终统计满足条件的对子数量。算法时间复杂度较高为 O(n^3),但对于题目限定的字符串长度范围(<= 100)是可以接受的。

标签:子串,1638,len,char,int,只差,字符串,sizeof
From: https://blog.csdn.net/qq_35085273/article/details/139410106

相关文章

  • 3. 无重复字符的最长子串
    给定一个字符串 s ,请你找出其中不含有重复字符的 最长 子串  的长度。  示例 1:输入:s="abcabcbb"输出:3解释:因为无重复字符的最长子串是"abc",所以其长度为3。示例2:输入:s="bbbbb"输出:1解释:因为无重复字符的最长子串是"b",所以其......
  • 力扣:5. 最长回文子串
    5.最长回文子串给你一个字符串 s,找到 s 中最长的 回文子串。示例1:输入:s="babad"输出:"bab"解释:"aba"同样是符合题意的答案。示例2:输入:s="cbbd"输出:"bb"提示:1<=s.length<=1000s 仅由数字和英文字母组成classSolution{publicStringlonges......
  • 5. 最长回文子串
    给你一个字符串s,找到s中最长的回文子串。示例1:输入:s="babad"输出:"bab"解释:"aba"同样是符合题意的答案。示例2:输入:s="cbbd"输出:"bb"提示:-1<=s.length<=1000-s仅由数字和英文字母组成......
  • 3.无重复字符的最长子串
    给定一个字符串s,请你找出其中不含有重复字符的最长子串的长度。示例1:输入:s="abcabcbb"输出:3解释:因为无重复字符的最长子串是"abc",所以其长度为3。示例2:输入:s="bbbbb"输出:1解释:因为无重复字符的最长子串是"b",所以其长度为1。示例3:输......
  • 【LeetCode】【5】最长回文子串
    文章目录@[toc]题目描述样例输入输出与解释样例1样例2提示Python实现动态规划个人主页:丷从心·系列专栏:LeetCode刷题指南:LeetCode刷题指南题目描述给一个字符串s,找到s中最长的回文子串样例输入输出与解释样例1输入:s="babad"输出:"bab"解释:"aba"同样是......
  • 5. 最长回文子串
    给你一个字符串s,找到s中最长的回文子串。示例1:输入:s="babad"输出:"bab"解释:"aba"同样是符合题意的答案。示例2:输入:s="cbbd"输出:"bb"classSolution{public:stringlongestPalindrome(strings){intn=s.size();if......
  • 【每日一题】最长回文子串
    5.最长回文子串给你一个字符串s,找到s中最长的回文子串。如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。示例1:输入:s="babad"输出:"bab"解释:"aba"同样是符合题意的答案。示例2:输入:s="cbbd"输出:"bb"提示:1<=s.length<=1000s仅由数字和英文......
  • ai网页详情页-测试-只差样式修改
    HTML代码<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><metaname="viewport"content="width=device-width,initial-scale=1.0"><title>ImageUploadandD......
  • 洛谷题单指南-动态规划2-P2679 [NOIP2015 提高组] 子串
    原题链接:https://www.luogu.com.cn/problem/P2679题意解读:在a中按顺序挑选k个子串,使得这些子串连在一起正好和b相等,求方案数。解题思路:这样的题目,无外乎两个思路:DFS暴搜(得部分分)、动态规划动态规划不好想,还是先暴搜吧!1、DFS暴搜搜索的思路就是:从a起始位置开始,一直找到跟b前......
  • 无重复字符的最长子串
    给定一个字符串s,请你找出其中不含有重复字符的最长子串的长度。示例1:输入:s="abcabcbb"输出:3解释:因为无重复字符的最长子串是"abc",所以其长度为3。示例2:输入:s="bbbbb"输出:1解释:因为无重复字符的最长子串是"b",所以其长度为1。示例3:输入:s......