《算法第四版》课后练习题1.2.6答案

习题1.2.6

如果字符串 s 中的字符循环移动任意位置之后能够得到另一个字符串 t，那么 s 就被称为 t 的回环变位（circular rotation）。例如，ACTGACG就是TGACGAC的一个回环变位，反之亦然。判定这个条件在基因组序列的研究中是很重要的。编写一个程序检查两个给定的字符串 s 和 t 是否互为回环变位。提示：答案只需要一行用到indexOf() ，length() 和字符串连接的代码。

要点分析

1. length()

该方法用于计算字符串的长度，如果s和t这两个字符串长度都不一样，就不可能是回环变位。

2. indexOf()方法

indexOf()方法用于返回一个指定字符在此字符串中第一次出现的索引。

3. String.contains()方法

String.contains()方法用于检查两个字符串是否有包含关系。

4. substring()

该方法用于根据指定索引范围截取字符串

5. charAt()

charAt()方法用于返回指定索引位置的字符

6. 代码实现

public class Test {
    public static void main(String[] args) {
        String s = "1234561";
        System.out.println(s.length());
        System.out.println(s.indexOf("345"));
        System.out.println(s.contains("123456"));
        System.out.println(s.substring(2));
        System.out.println(s.substring(2,5));
        System.out.println(s.charAt(0));

    }
}

输出：
7
2
true
34561
345
1

7. 方法一

为什么上面介绍了这么多方法呢，因为这道题有很多种好玩的做法。方法一也就是最笨的方法，将字符串s，依次遍历，每次遍历的时候，都将字符串拆成两份，然后再组成一份看是否和t相等。当然遍历也有两种方法，本文答案第二种方法的遍历更加简单[1] 。

8. 方法二

也就是课本中给的提示，用indexOf方法。该方法非常的有意思，只用一行代码就解决了问题[2]。该方法的原理如下。

比如字符串s为ABC，而字符串t为BCA，因为t + t 为BCABCA ，所以t + t 是包含字符串s的

那么(t + t).indexOf(s)的返回值必大于等于0，也就是说(t + s).indexOf(s) >= 0) 则s和t为回环变位。这个方法简直太有趣了。同理，我们可以将indexOf换成contains方法，原理是一样的，也就是方法三。

参考答案

/**
 * @description:
 * @author: ZhangJia
 * @create: 2018-08-07 17:05
 **/
public class Six {
    public static void main(String[] args) {
        String s = "ACTGACG";
        String t = "ACGACTR";
//        String t = "TGACGAC";

        System.out.println(isCircularRotation(s, t));
        System.out.println(isCircularRotation1(s, t));
        System.out.println(isCircularRotation2(s, t));
        System.out.println(isCircularRotation3(s, t));

    }

    /**
     * @description: 依次遍历法1
     * @param: s 字符串s
     * @param: t 字符串t
     * @return: s 和 t 是否互为回环变位
     */

    public static boolean isCircularRotation(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int length = s.length();
        for (int i = 1; i <= length; i++) {
            String left = s.substring(0, i);
            String right = s.substring(i, length);
            if ((right + left).equals(t)) {
                return true;
            }
        }
        return false;
    }

    /**
     * @description: 依次遍历法2
     * @param: s 字符串s
     * @param: t 字符串t
     * @return: s 和 t 是否互为回环变位
     */

    public static boolean isCircularRotation1(String s, String t) {
        if (s.length() != t.length()) return false;

        for (int i = 0, len = t.length(); i < len; i++) {
            if (s.equals(t)) return true;
            s = s.substring(1) + s.charAt(0);
        }

        return false;
    }


    /**
     * @description: indexof方法
     * @param: s 字符串s
     * @param: t 字符串t
     * @return: s 和 t 是否互为回环变位
     */
    public static boolean isCircularRotation2(String s, String t) {
        return (s.length() == t.length()) && ((t + t).indexOf(s) >= 0);
    }

    /**
     * @description: contains方法
     * @param: s 字符串s
     * @param: t 字符串t
     * @return: s 和 t 是否互为回环变位
     */
    public static boolean isCircularRotation3(String s, String t) {
        return s.length() == t.length() && (t + t).contains(s);
    }


}

输出：
true
true
true
true