[google面试CTCI] 1-8.判断子字符串


		【字符串与数组】
 
Q：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。书写代码来判断S2是否能通过旋转S1得到。（只能使用一次isSubstring方法）
 
解答：
 
 
以waterbottle和erbottlewat为例，我们只有使用一次isSubstring的机会，但是单单从这两个字符串来看，我们找不到彼此之间的子串关系。因此，可以考虑去改变、构造(几何里的做辅助线)字符串。要判断S2是否能通过旋转S1得到，我们可以先将S1扩展成S1S1，即erbottlewat扩展成erbottlewaterbottlewat,然后再判断S2是否为S1S1的子串。当然，将S2扩展成S2S2,然后再判断S1是否为S2S2的子串是同样的道理。
代码如下所示：
 
int is_rotation(char* str1,char* str2){
int len1=strlen(str1);
int len2=strlen(str2);
if(len1!=len2)
return 0;
char* newStr=malloc(len1*sizeof(char));
strcpy(newStr,str1);
strcat(newStr,str1);
int rValue;
rValue=isSubString(newStr,str2);
free(newStr);
return rValue;
}
上面代码中的isSubString是字符串匹配算法，最著名的有KMP算法、BM算法等，其思想及其具体实现，可以查看博客里的另外两篇文章。

补充：综合编程 , 其他综合 ,