编程之美-3.1 字符串移位包含问题 笔记

假设字符串s1=AABCD,s2=CDAA,判断s2是否可以通过S1的循环移位得到字符串包含。
 如 s1移两位： 1.ABCDA->2.BCDAA 则此时包含了 S2="CDAA"

 解题思路：
 分解s1的循环移位得到：
 AABCD,ABCDA,BCDAA,CDAAB,.....
 如果我们将前面移走的字符串保留下来，则有：
 AABCD,AABCDA,AABCDAA,AABCDAAB,AABCDAABC,AABCDAABCD

这里，我们可以发现，实际对s1的循环移位得到的字符串实际为s1s1。
那么我们判断s2是否可以通过s1循环移位得到包含，则只需要判断s1s1中是否含有s2即可以。
用提高空间复杂度来换取时间复杂度的减低的目的。
java代码如下：

public class StrigMove{
    public static void main (String[] args) {
        String s1="AABCD";
        String s2="CDAA";
        if(s1.concat(s1).indexOf(s2)!=-1){
            System.out.println ("true");
        }else{
            System.out.println ("false");
        }
       
    }
}

 

 

评论

3 楼 gogole_09 2009-12-23  

bcccs 写道

唉，strlen(s2)>strlen(s1)的时候呢？

而且，indexof的时间复杂度呢？难不成你以为可爱的java sdk里的函数都时间复杂度都是O（1）？

这位朋友，请看清楚题目， 是“判断s2是否可以通过S1的循环移位得到字符串包含” 既是包含，应该就不会有上述strlen(s2)>strlen(s1)的情况吧。
  另外，也对谢你的提醒，
  对于indexof的时间复杂度问题，查看了下源代码，对是否为o(1)确实有点疑问.

2 楼 bcccs 2009-10-23  

唉，strlen(s2)>strlen(s1)的时候呢？

而且，indexof的时间复杂度呢？难不成你以为可爱的java sdk里的函数都时间复杂度都是O（1）？

1 楼 busy12377 2009-10-22  

有点意思！