[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算法等,其思想及其具体实现,可以查看博客里的另外两篇文章。


作者:Viidiot  微信公众号:linux-code


上一篇:uart串口协议


下一篇:Android开发目录