leetcode-686-Repeated String Match(重复多少次A能够找到B)

题目描述:

Given two strings A and B, find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution, return -1.

For example, with A = "abcd" and B = "cdabcdab".

Return 3, because by repeating A three times (“abcdabcdabcd”), B is a substring of it; and B is not a substring of A repeated two times ("abcdabcd").

Note: The length of A and B will be between 1 and 10000.

要完成的函数:

int repeatedStringMatch(string A, string B) 

说明:

1、给定两个字符串A和B,要求判断需要重复A几次,才能在A中找到B,也就是使B成为A的子串。返回重复的最小次数。

2、这道题题意清晰,解决题目的关键在于把可能的情况想清楚。

本题分为三种情况处理:

① A比B短,这是最容易想到的情况,比如A为“abc”,B为“bcab”,我们要重复1次,使得A的长度大于等于B。接着猜判断B能不能在A中找到,这时我们用find函数即可。

  还有另一种情况,A重复完之后刚好长度等于B,但是我们有时能找到B,有时还要再重复一次才能找到B。

     比如A为“abc”,B为“abcabc”,这种就是重复1次,长度刚好等于B,能找到B的情况。

     比如A为“abc”,B为“bcabca”,这种就是重复1次,长度刚好等于B,但不能找到B的情况,要再重复1次。

② A比B长,有两种情况,第一种就是刚好能找到,不用重复。比如A为“abcdefg”,B为“bcd”。

  另一种是找不到,要再重复一次,比如A为“abcdefg”,B为“efga”,要再重复一次才能找到。

③ A和B一样长,同样两种情况,第一种就是刚好能找到,A==B

     另一种就是要再重复一次,比如A为“abcdefg”,B为“efgabcd”,要再重复一次才能找到。

综上所述,我们使得A的长度大于等于B,如果这个时候能找到B,那么ok,返回重复的次数。

如果不能找到B,那么再重复一次A,如果重复之后能找到,那么返回新的重复的次数。

如果还是找不到,我们认为当A的长度大于等于B的时候,这时候可能还会找不到B,但如果再重复一次A,重复之后还是找不到B,那么就是不可能通过重复A来找到B的,返回-1。(这一点不认同的同学们可以自己再想一想,有问题欢迎在下方评论区交流)

代码如下:(附详解)

    int repeatedStringMatch(string A, string B) 
    {
        string newA;
        int count=0;
        while(newA.size()<B.size())//重复A使得newA的长度大于等于B
        {
            newA+=A;
            count++;//记录重复的次数
        }
        if(newA.find(B)!=-1)//如果找得到,返回重复次数
            return count;
        newA+=A;//如果找不到,再重复一次A
        if(newA.find(B)!=-1)//如果找得到,返回新的重复次数
            return ++count;
        return -1;//如果还是找不到,返回-1
    }

上述代码实测17ms,beats 82.81% of cpp submissions。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏猿人谷

第一个只出现一次的字符

题目:在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff,则输出b。 看到这道题时,最直观的想法是从头开始扫描这个字符串中的每个字符。当访问到某...

20070
来自专栏快乐八哥

JavaScript中匿名函数的困惑

函数字面量(function literal):处理事件的无名函数(nameless function)。函数字面量有时也称为匿名函数(anonymous fu...

19470
来自专栏开发与安全

从零开始学C++之从C到C++(一):const与#define、结构体对齐、函数重载name mangling、new/delete 等

一、bool 类型 逻辑型也称布尔型,其取值为true(逻辑真)和false(逻辑假),存储字节数在不同编译系统中可能有所不同,VC++中为1个字节。 声明方式...

20400
来自专栏JetpropelledSnake

Python学习笔记之Python正则表达式指南

正则表达式并不是Python的一部分。正则表达式是用于处理字符串的强大工具,拥有自己独特的语法以及一个独立的处理引擎,效率上可能不如str自带的方法,但功能十分...

22010
来自专栏mathor

LeetCode3. 无重复字符的最长子串

 首先定义一个Map<Character,Integer>用来保存当前字符最后一次出现的下标位置。再定义一个pre数组,用来保存以每一个字符为结尾的最长无重...

53920
来自专栏牛肉圆粉不加葱

[7] - trait

这是我以前在知乎上看到关于类继承作用的回答,虽不完全正确,却十分明确的表达出了好的代码应避免类继承而尽量使用类组合。Scala 显然也非常赞同这一点,以至于有了...

12920
来自专栏python3

python3--小数据池,is,字符编码

python3x中的str在内存中的编码方式是unicode. python3x中的str不能直接存储和发送

25110
来自专栏java一日一条

(转)Java正则表达式入门

众所周知,在程序开发中,难免会遇到需要匹配、查找、替换、判断字符串的情况发生,而这些情况有时又比较复杂,如果用纯编码方式解决,往往会浪费程序员的时间及精力。因此...

13010
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-12(02)总结Scanner,String

(6)字符串的案例 A:模拟用户登录 B:字符串遍历 C:统计字符串中大写,小写及数字字符的个数 D:把字符串的首字母转成大写,其他小写 E:把int...

430100
来自专栏猿人谷

不用加减乘除做加法

题目:写一个函数,求两个整数之和,要求在函数体内不得使用+、-、×、÷四则运算符号。 分析: 第一步:不考虑进位对每一位相加。0加0、1加1的结果都是0,0加1...

22970

扫码关注云+社区

领取腾讯云代金券