798
技術社區[雲棲]
CareerCup之1.8 字符串移位包含問題
【題目】
原文：
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;
}
最後更新：2017-04-03 12:56:39