首页 > 代码库 > 循环移动字符串
循环移动字符串
这个问题的意思就是给定两个字符串s1和s2,判断s2是否包含在s1循环移位得到的字符串中。
这个题的最简单的一种思路就是对s1进行循环穷举,对于得到的每种情况,都进行判断s2是否包含在其中。
不过如果s1的字符串很长,那么穷举的时间复杂度是相当高的。因此可以换一种思路。
新的解决办法相当的巧妙,假设我们在s1字符串前面再加入一个跟s1登场的空间,每当s1循环移动之后,就把移到末尾的字符在前面空间中加一个,那么情况如下所示:
ABCD----ABCDA----ABCDAB----ABCDABC----ABCDABCD
如果s2在s1的循环移位中,那么一定就在s1s1中。显然我们只需要多一个n的空间,即可将时间复杂度降到很低。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。