大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
【称号】
原文:
1.8 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”的旋转字符串。
【分析】
我们也能够对循环移位之后的结果进行分析。
以S1 = ABCD为例,先分析对S1进行循环移位之后的结果,例如以下所看到的:
ABCD—>BCDA—->CDAB—->DABC—->ABCD……
如果我们把前面的移走的数据进行保留。会发现有例如以下的规律:
ABCD—>ABCDA—->ABCDAB—->ABCDABC—->ABCDABCD……
因此,能够看出对S1做循环移位所得到的字符串都将是字符串S1S1的子字符串。
假设S2能够由S1循环移位得到,那么S2一定在S1S1上,这样时间复杂度就减少了。
相同题目:编程之美之字符串移位包括问题
【代码一】
/********************************* * 日期:2014-5-15 * 作者:SJF0115 * 题号: 字符串移位包括问题 * 来源:CareerCup **********************************/ #include <iostream> #include <stdio.h> #include <string.h> using namespace std; bool isSubstring(char* str1,char* str2){ if(str1 == NULL || str2 == NULL){ return false; } if(strstr(str1,str2) != 0){ return true; } return false; } bool IsRotate(char* str1,char* str2){ int i,j; if(str1 == NULL || str2 == NULL){ return false; } int len1 = strlen(str1); char* str3 = new char(len1*2+1); strcpy(str3,str1); strcat(str3,str1); //str3 = str1+str1 if(isSubstring(str3,str2)){ return true; } return false; } int main(){ char str1[6] = "AABCD"; char str2[5] = "CDAA"; bool result = IsRotate(str1,str2); cout<<result<<endl; return 0; }
【代码二】
/********************************* * 日期:2014-5-15 * 作者:SJF0115 * 题号: 字符串移位包括问题 * 来源:CareerCup **********************************/ #include <iostream> #include <stdio.h> #include <string.h> using namespace std; bool isSubstring(string str1,string str2){ if(str1.find(str2) != string::npos) { return true; } return false; } bool IsRotate(string str1,string str2){ string str3 = str1+str1; if(isSubstring(str3,str2)){ return true; } return false; } int main(){ string str1 = "apple"; string str2 = "pleap"; bool result = IsRotate(str1,str2); cout<<result<<endl; return 0; }
版权声明:本文博客原创文章,博客,未经同意,不得转载。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117665.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...