首页 > 代码库 > 判断s2是否能够被通过s1做循环移位(rotate)得到的字符串是否包含
判断s2是否能够被通过s1做循环移位(rotate)得到的字符串是否包含
问题:给定两个字符串s1和s2,要求判断s2是否能够被通过s1做循环移位(rotate)得到的字符串包含。例如,S1=AABCD和s2=CDAA,返回true;给定s1=ABCD和s2=ACBD,返回false。
看到 这里的一个思路 字符串移位包含的问题(编程之美)
引用原文
“
解法二:我们也可以对循环移位之后的结果进行分析。
以S1 = ABCD为例,先分析对S1进行循环移位之后的结果,如下所示:
ABCD--->BCDA---->CDAB---->DABC---->ABCD……
假设我们把前面的移走的数据进行保留,会发现有如下的规律:
ABCD--->ABCDA---->ABCDAB---->ABCDABC---->ABCDABCD……
因此,可以看出对S1做循环移位所得到的字符串都将是字符串S1S1的子字符串。如果S2可以由S1循环移位得到,那么S2一定在S1S1上,这样时间复杂度就降低了。
”
代码如下:为什么不封装呢?你猜。
1 static void Main(string[] args) 2 { 3 4 String s1="ABDDE"; 5 String s2="DDAB"; 6 string s3=string.Concat(s1,s1); 7 if (s3.Contains(s2)) 8 { 9 Console.WriteLine("true"); 10 }else{11 Console.WriteLine("false"); 12 } 13 Console.ReadKey();14 15 }
------再一次站在巨人的肩膀上
判断s2是否能够被通过s1做循环移位(rotate)得到的字符串是否包含
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。