01.09字符串轮转

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// 暴力法
    // 如果 s2 是由 s1 旋转而来 则从头到位开始旋转s1
    // 遍历旋转0位(原字串)， 1位... 直到旋转到倒数第二位
    // 如果遍历过程中，有跟s2相同的字符串， 则return true
    // 遍历一遍完后，都没有相同字符串， 则return false
    public boolean isFlipedString1(String s1, String s2) {

        if ((s1 == null && s2 == null) || (s1.length() == 0 && s2.length() == 0)) return true;
        if (s1 == null || s2 == null) return false;
        if (s1.length() != s2.length()) return false;

        int i = 0;
        StringBuilder sb = new StringBuilder();
        while (i < s1.length()){

            sb.delete(0,sb.length());
            sb.append(s1.substring(i, s1.length()));
            sb.append(s1.substring(0,i));
            if (sb.toString().equals(s2)) return true;
            i++;
        }
        return false;
    }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

		// 题目中有说明， 你能只调用一次检查子串的方法吗？
    // 显然上述解题，不符合检查一次字串的要求。拼接了N次字串，比较了N次字串
    // 上述方法时间复杂度 : O(N ^ 2)
    // 空间复杂度 : O(1)
    // 时间复杂度非常高，算法虽过了，但是用时很长
    // 接下来，我们尝试做时间复杂度的优化

    // 思路是 裁剪字串成两个子串
    // 从头到位比较,当字串s1 i位置， 与字串s2的0位置，字符相同时，根据i分割两个字串
    // 如果s1 和 s2 分割后，两部分分别都相同，说明是旋转字串
    // 如果不相同， 则往下遍历下一个与 s2 0位置相同的元素。
    // i遍历完， 即与s2 0号位置相同的字符又两部分分别相同的字串。 则return false

    // 我们的时间复杂度有了大幅度的提升，截图中可以看出，由之前的40ms左右，提高到1ms左右。
    // 时间复杂度 : O(N)
    // 空间复杂度 : O(1)
    public boolean isFlipedString2(String s1, String s2){

        if ((s1 == null && s2 == null) || (s1.length() == 0 && s2.length() == 0)) return true;
        if (s1 == null || s2 == null) return false;
        if (s1.length() != s2.length()) return false;

        int i = 0,len = s1.length();
        while ((i < len)){
            if (s1.charAt(i) != s2.charAt(0)){
                i ++;
                continue;
            }

            String l_s1 = s1.substring(0,i);
            String r_s1 = s1.substring(i,len);

            String l_s2 = s2.substring(0,len - i);
            String r_s2 = s2.substring(len - i,len);

            if (l_s1.equals(r_s2) && r_s1.equals(l_s2)) return true;
            i++;
        }

        return false;
    }

1
2
3
4
5
6

    public boolean isFlipedString(String s1, String s2){
        if ((s1 == null && s2 == null) || (s1.length() == 0 && s2.length() == 0)) return true;
        if (s1 == null || s2 == null || s1.length() != s2.length()) return false;
        
        return (s1 + s1).contains(s2);
    }