首页 > 代码库 > 编程之美之字符串移位包含问题
编程之美之字符串移位包含问题
【题目】
给定两个字符串s1和s2,要求判断s2是否能够被通过s1做循环移位(rotate)得到的字符串包含。例如,S1=AABCD和s2=CDAA,返回true;给定s1=ABCD和s2=ACBD,返回false。
【分析】
【思路一】
从题目中可以看出,我们可以使用最直接的方法对S1进行循环移动,再进行字符串包含的判断,从而遍历其所有的可能性。
字符串循环移动,时间复杂度为O(n),字符串包含判断,采用普通的方法,时间复杂度为O(n*m),总体复杂度为O(n*n*m)。
字符串包含判断,若采用KMP算法,时间复杂度为O(n),这样总体的复杂度为O(n*n)。若字符串的长度n较大,显然效率比较低。其中n为S1的长度,m为S2的长度。
【思路二】
我们也可以对循环移位之后的结果进行分析。
以S1 = ABCD为例,先分析对S1进行循环移位之后的结果,如下所示:
ABCD--->BCDA---->CDAB---->DABC---->ABCD……
假设我们把前面的移走的数据进行保留,会发现有如下的规律:
ABCD--->ABCDA---->ABCDAB---->ABCDABC---->ABCDABCD……
因此,可以看出对S1做循环移位所得到的字符串都将是字符串S1S1的子字符串。如果S2可以由S1循环移位得到,那么S2一定在S1S1上,这样时间复杂度就降低了。
【代码一】
/********************************* * 日期:2014-5-15 * 作者:SJF0115 * 题号: 字符串移位包含问题 * 来源:编程之美 **********************************/ #include <iostream> #include <stdio.h> #include <string.h> using namespace std; bool IsRotate(char* str1,char* str2){ int i,j; if(str1 == NULL || str2 == NULL){ return false; } int len = strlen(str1); //循环移位 for(i = 0;i < len;i++){ char temp = str1[0]; //移动一位 for(j = 1;j < len;j++){ str1[j-1] = str1[j]; } str1[len-1] = temp; //判断str1中是否包含str2 if(strstr(str1,str2) != 0){ 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 * 题号: 字符串移位包含问题 * 来源:编程之美 **********************************/ #include <iostream> #include <stdio.h> #include <string.h> using namespace std; 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(strstr(str3,str2) != 0){ return true; } return false; } int main(){ char str1[6] = "AABCD"; char str2[5] = "CDAA"; bool result = IsRotate(str1,str2); cout<<result<<endl; return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。