leetcode-796-Rotate String

题目描述:

We are given two strings, A and B.

shift on A consists of taking string A and moving the leftmost character to the rightmost position. For example, if A = 'abcde', then it will be 'bcdea' after one shift on A. Return True if and only if A can become B after some number of shifts on A.

Example 1:
Input: A = 'abcde', B = 'cdeab'
Output: true

Example 2:
Input: A = 'abcde', B = 'abced'
Output: false

Note:

  • A and B will have length at most 100.

要完成的函数:

bool rotateString(string A, string B) 

说明:

1、给定两个字符串A和B,要求判断这两个字符串,可不可以通过不断地把A中的首字母搬到末尾去,最终把A变成B。比如A为abcde,B为cdeab,就是可以通过前述操作把A变成B的。

2、明白题意,笔者最开始觉得这种结构很熟悉,应该是队列的操作,可以定义一个队列,把A中的字母塞到队列中去,然后不断地取出首位,插入到末位,判断是不是能形成B字符串。

不过这样子还要定义一个队列,操作略显麻烦,直觉这样做并不是最简便的方法。

之后想到其实找到B首字母,比如上面给的例子,A是abcde,B是cdeab,B中首字母是c,那么找到c在A中的位置j,然后逐位比较A[j]和B[i](i从0开始)是否相等,这是A中后半部分的比较。

然后再比较A中前半部分是否与B中剩余部分相等。我们已知了j的位置,这些操作都是非常容易的。

这道题就可以做出来了。

不过,当碰到B中首字母在A中多次出现,而且首次出现还匹配不上,得第二次才匹配上的情况,比如A是abcdecdf,B是cdfabcde。

如果只是一次搜索,c在A中位置是第三位,这时匹配不成功。

但如果c在A中位置是倒数第三位那里,这时候的匹配就是成功的。

所以之前的做法就得在外面再加多个循环,一直迭代,直到搜索到能匹配的位置。

代码如下:(附详解)

    bool rotateString(string A, string B) 
    {
        int i=0,j=0,s1=A.size(),s2=B.size();
        if(s1!=s2)//边界条件
            return false;
        if(s1==0)//边界条件,比如A和B都是空字符串
            return true;
        bool flag;
        while(j<s1)//j用于表示B的首字母在A中的哪个位置
        {
            while(j<s1)//一直搜索,直到找到B中首字母在A中的位置
            {
                if(B[0]==A[j])
                    break;
                j++;
            }
            flag=1;
            i=0;
            int t1=1,t2=j+1;//t1表示B中尝试匹配的起始位置,t2表示A中尝试匹配的起始位置
            while(t2<s1)
            {
                if(B[t1]!=A[t2])
                {
                    flag=0;
                    break;
                }
                t1++;
                t2++;
            }
            if(flag==1)//如果上述匹配能成功,那么进行剩余部分的匹配
            {
                while(t1<s1)
                {
                    if(B[t1]!=A[i])
                    {
                        flag=0;
                        break;
                    }
                    t1++;
                    i++;
                }
            }
            if(flag==1)//如果两个部分都匹配成功了,那么返回true
                return true;
            j++;//如果没有匹配成功,那么j++,搜索B中首字母在A中的下一个出现位置
        }
        return false;//如果搜索到A的末尾,每一次都不能匹配成功,那么返回false
    }

上述代码实测3ms,beats 97.87% of cpp submissions。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏IT可乐

Java数据结构和算法(十三)——哈希表

  Hash表也称散列表,也有直接译作哈希表,Hash表是一种根据关键字值(key - value)而直接进行访问的数据结构。它基于数组,通过把关键字映射到数组...

31080
来自专栏Vamei实验室

Python深入01 特殊方法与多范式

Python一切皆对象,但同时,Python还是一个多范式语言(multi-paradigm),你不仅可以使用面向对象的方式来编写程序,还可以用面向过程的方式来...

21950
来自专栏文武兼修ing——机器学习与IC设计

调度队列的优先堆实现应用场景模拟应用分析代码实现

应用场景模拟 考虑优先堆的一种应用场景——按优先级的任务调度队列:每个任务有一个优先级和唯一标号,该调度队列需要具有以下功能: 添加任务:将任务添加进调度队列并...

367100
来自专栏orientlu

读 《C Traps and Pitfalls》Record

单引号实际代表一个整数 双引号代表指向无名数组的起始字符的指针(字符结尾 0) 使用库函数计算得到的字符串长度不包括结尾的0!

12130
来自专栏Java架构师学习

为Java程序员金三银四精心挑选的五十道面试题与答案

1、面向对象的特征有哪些方面? 【基础】 答:面向对象的特征主要有以下几个方面: 1)抽象:抽象就是忽略一个主题中与当前目标无关的那些方面,以便更充分地...

37160
来自专栏容器云生态

awk-grep-sed简单使用总结(正则表达式的应用)

正则表达式: 匹配一组字符: #[ns]a.\.xls  //[]用于限定字符;“.”用于匹配任意字符; \.用于转义"." 匹配到s/na*.xls  [n...

28890
来自专栏农夫安全

python爬虫基础之正则表达式

Python基础前期后后看了五六遍,除了能读懂一些简单的代码,一直也没有进阶。 这次借助一个爬虫教学视频。把学习中的一些重点写下来,一个是自己巩固,一个是也帮助...

44170
来自专栏SeanCheney的专栏

《利用Python进行数据分析·第2版》第3章 Python的数据结构、函数和文件3.1 数据结构和序列3.2 函数3.3 文件和操作系统3.4 结论

本章讨论Python的内置功能,这些功能本书会用到很多。虽然扩展库,比如pandas和Numpy,使处理大数据集很方便,但它们是和Python的内置数据处理工具...

47960
来自专栏数据结构与算法

1470 数列处理

个人博客:doubleq.win 1470 数列处理  时间限制: 1 s  空间限制: 1000 KB  题目等级 : 青铜 Bronze 题解 题目描述 D...

27550
来自专栏飞雪无情的博客

Go语言实战笔记(七)| Go 类型

Go 语言是一种静态类型的编程语言,所以在编译器进行编译的时候,就要知道每个值的类型,这样编译器就知道要为这个值分配多少内存,并且知道这段分配的内存表示什么。

9030

扫码关注云+社区

领取腾讯云代金券