经典算法面试题目-判断s2是否是s1的旋转字符串(1.8)-阿里云开发者社区

开发者社区> 谙忆> 正文

经典算法面试题目-判断s2是否是s1的旋转字符串(1.8)

简介: 题目 Assume you have a method isSubstring which checks if one word is a substring of another.
+关注继续查看

题目

Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring ( i.e., “waterbottle” is a rotation of “erbottlewat”).

假设你有一个isSubstring函数,可以检测一个字符串是否是另一个字符串的子串。 给出字符串s1和s2,只使用一次isSubstring就能判断s2是否是s1的旋转字符串, 请写出代码。
例如:”waterbottle”是”erbottlewat”的旋转字符串。

解答

题目说我们使用一次isSubstring函数就可以判断s2是否是s1的旋转字符串, 如果从原始字符串s1和s2直接入手肯定不行,因为它们根本不存在子串关系。 如果不断地旋转字符,然后调用isSubstring,又需要调用多次的isSubstring。 而且通过旋转字符再判断,可以直接用等号判断,根本用不上isSubstring。

既然如此,我们就要考虑去改变原始字符串。要判断a串是否是b串的子串, 一般情况下都会有b串长度大于a串,长度相等的话就直接判断它们是不是相等的串了。 我们可以考虑把串s1变长,然后调用一次isSubstring判断s2是否是s1变长后的子串, 如果是,就得出s2是s1的旋转字符串。s1怎么变长呢?无非就是s1+s1或是s1+s2, s2一定是s1+s2的子串,因此这样做没有任何意义。而s1+s1呢? 我们就上面的例子进行讨论:s1=waterbottle,s2=erbottlewat. 则:

s1 + s1 = waterbottlewaterbottle

很容易可以发现,s1+s1其实是把s1中每个字符都旋转了一遍,而同时保持原字符不动。 比如waterbottle向右旋转2个字条应该是:terbottlewa,但如果同时保持原字符不动, 我们得到的就是waterbottlewa,而terbottlewa一定是waterbottlewa的子串, 因为waterbottlewa只是在terbottlewa的基础上再加上一条原字符不动的限制。 因此s1+s1将包含s1的所有旋转字符串,如果s2是s1+s1的子串,自然也就是s1 的旋转字符串了。

首先,我们来了解一个函数:
a.find(b) 表示查找字符串a是否包含子串b,若查找成功,返回按查找规则找到的第一个字符或子串的位置;若查找失败,返回npos,即-1(打印出来为4294967295)。

接下来,利用这个函数,我们可以很方便的写出判断s2是否是s1的旋转字符串的代码。

关键代码:

//判断s2是不是s1的子串
bool isSubstring(string s1, string s2){
    if(s1.find(s2) != string::npos) return true;
    else return false;
}

//防范一下,以及调用:isSubstring(s1+s1, s2)
bool isRotation(string s1, string s2){
    if(s1.length() != s2.length() || s1.length()<=0)
        return false;
    return isSubstring(s1+s1, s2);
}

完整代码:

#include <iostream>
#include <string>
using namespace std;

bool isSubstring(string s1, string s2){
    //a.find(b)查找字符串a是否包含子串b。string::npos(很大的无符号整数)也可以认为就是-1。
    if(s1.find(s2) != string::npos) return true;
    else return false;
}
bool isRotation(string s1, string s2){
    //防范一下!如果s2的长度和s1的不相等,肯定就不可能s2是s1的旋转子串了。
    if(s1.length() != s2.length() || s1.length()<=0)
        return false;
    return isSubstring(s1+s1, s2);
}

int main(){
    string s1 = "apple";
    string s2 = "pleap";
    if(isRotation(s1, s2)){
        cout<<s2+"是"+s1+"的旋转字符串"<<<<endl;
    }
    //cout<<string::npos<<endl; //4294967295
    //cout<<s1.find(s2)<<endl;  //4294967295
    return 0;
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
数据分析与挖掘的经典算法
最近看到一篇文章介绍了数据分析与挖掘的十大经典算法:C4.5,K-Means,SVM,Apriori,EM,PageRank,AdaBoost,KNN,Native Bayes,CART。
2362 0
任务调度:时间轮算法经典案例解析及应用实现
平时大家的工作中应该会遇到较多需要在某个时间点执行某个任务,比如对运维来说,定时数据库的备份,日志和监控信息的抓取;比如业务系统,某个时间点给某个人群用户发放优惠券,甚至从操作系统角度,人机交互进程、视频播放的实时进程、批处理的后台进程等进程间的调度。。。 所以如何将这些任务高效、精准的调度?是任务调度系统中最重要的命题,当然在业务系统中一个完善的任务调度系统是很复杂的,需要具备能调度、可视化管理、过程可追溯、结果可分析、持久化、高可用等特性,这篇文章主要讨论任务调度逻辑,其余的内容我们后面文章探讨。
114 0
算法:字符串消除问题的数学证明
问题: 给定一个字符串,仅由A、B、C3个字母组成。当出现连续两个不同的字母时,你可以用另外一个字母替换它,如有AB或BA连续出现,你把它们替换为字母C;有AC或CA连续出现时,你可以把它们替换为字母B;有BC或CB连续出现时,你可以把它们替换为字母A。
477 0
经典算法面试题目-判断s2是否是s1的旋转字符串(1.8)
题目 Assume you have a method isSubstring which checks if one word is a substring of another.
810 0
经典算法面试题目-矩阵旋转90度(1.6)
题目 Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place? 一张图像表示成NxN的矩阵,图像中每个像素是4个字节,写一个函数把图像旋转90度。
2220 0
[leetcode/lintcode 题解] 算法面试真题:BST的中序前驱节点
[leetcode/lintcode 题解] 算法面试真题:BST的中序前驱节点
193 0
经典算法面试题目-置矩阵行列元素为0(1.7)
题目 Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0. 写一个函数处理一个MxN的矩阵,如果矩阵中某个元素为0,那么把它所在的行和列都置为0. 解答 简单题。
865 0
经典算法详解(9)寻找丑数
题目:我们把只含有因子2、3、5的数称为丑数。例如6、8都是丑数,而14不是丑数,因为它含有因子7.通常也把1当做丑数。编程找出1500以内的全部丑数。注意:使用的算法效率应尽量高。 C++实现: 1 #include 2 3 using namespace std; 4 5 //判...
1296 0
经典算法详解(10)图中有多少个三角形
题目:请说出下面图形中包含多少个三角形?请用一个程序完成计算。 C++版本 1 #include 2 3 using namespace std; 4 5 const char NO_POINT = '0'; 6 7 //任意的一条线 8 const char *map[]...
3694 0
+关注
谙忆
GitHub: https://github.com/chenhaoxiang
714
文章
40
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载