博客主页 🏗️
wy的leetcode刷题记录_Day63_复工开始!
wy的leetcode刷题记录_Day63_复工开始!

Author:

wy-1226

©

Wordage:

共计 2002 字

needs:

约 2 分钟

Popular:

196 ℃

Created:

目 录

wy的leetcode刷题记录_Day63_复工开始!

声明

本文章的所有题目信息都来源于leetcode
如有侵权请联系我删掉!
时间:

前言

考研期间只保持每日一题和可有可无的随机题
@TOC

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

今天的每日一题是:1638. 统计只差一个字符的子串数目

题目介绍

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

比方说, "computer" and "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

思路

枚举大法:
理解题意之后可以概括为:比较字符串s的字串中是否与t字符串的任意子串差距为1(差距:不同字符串的个数)。整体解法为:使用指针i表示遍历到s字符串的子串的起始位置,指针j表示遍历到t字符串的子串的起始位置,使用计步器k来表示俩个字符串从起始位置的出发距离(子串长度)。外层循环是字符串的起始位置,内层循环是走的步数。使用全局变量ans表示符合条件的字串个数,局部变量diff表示当前走的步数的俩个子串的差距。局部变量diff:1.当diff>1的时候不符合题目条件不需要继续走下去了,变量k的循环可以中断了,然后更新俩个字符串其中之一的起点。2.每更新一次起点diff都需要重新置0。ans:每当走一步之后diff仍然是1,那么当前子字符串符合条件,ans++。

代码

class Solution {
public:
    int countSubstrings(string s, string t) {
        int s1=s.size();
        int t1=t.size();
        
        int ans=0;

        for(int i=0;i<s1;i++)
        {
            for(int j=0;j<t1;j++)
            {
                int diff=0;
                for(int k=0;k+i<s1&&k+j<t1;k++)
                {
                    diff+=(s[i+k]==t[j+k]?0:1);
                    if(diff>1)
                        break;
                    else if(diff==1)
                        ans++;   
                    }

            }
        }
        return ans;
    }
};

收获

复工日记!题目还是比较简单的。

文章二维码
wy的leetcode刷题记录_Day63_复工开始!
共计 0 条评论,点此发表评论
博客主页 wyのblog I know you are here. 百度统计
鄂ICP备2023003777号-1 本站已运行 324 天 13 小时 55 分 自豪地使用 Typecho 建站,并搭配 MyDiary 主题 Copyright © 2023 ~ 2024. wyのblog All rights reserved.
打赏图
打赏博主
欢迎
搜 索
足 迹
分 类
  • 默认分类
  • Code
  • 日记
  • 音乐
  • 游戏
  • 阅读
  • 计划
  • 图片
  • 旅游
  • 影视