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

背景

这是《编程之美》一书中3.1节字符串移位包含问题的Java实现。

题目

给定两个字符串s1和s2, 要求判定s2是否能够被通过s 作循环移位 ( rotate )得到的字符串包含。例如, 给定s1 = AABCD和s2 = CDAA,返回 true;给定s1 = ABCD和s2 = ACBD, 返回 false。

Java实现

暴力求解

最直接的方法就是对s1进行循环移位，再进行字符串包含的判断，从而遍历其所有的可能性。

空间换时间

通过观察可以发现，只要判断s2是否在两个s1中就可以了。下面给出Java实现：

import java.util.*;

public class Stringshift {
    public static boolean contains(String src, String dst) {
        String srcsrc = src.concat(src);

        if (srcsrc.contains(dst)) {
            return true;
        } else {
            return false;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Scanner in2 = new Scanner(System.in);
        String s1 = in.nextLine();
        String s2 = in2.nextLine();
        System.out.println(contains(s1, s2));
    }
}

折中

还有一种方法就是不用申请过多的空间，直接对s1循环来比较，超过了就取余，也就是相当于延长了字符串了。