String Rotation Check

medium Strings

Two words are given. Print true if the second word can be made by moving some first letters of the first word to its end (a rotation). Print false otherwise.

Constraints

1 <= length <= 1000

Examples

Input

waterbottle erbottlewat

Output

true

Substring search
Rotation trick

Solutions

Best approachTime O(n^2) worst case with simple searchSpace O(n)

Writing the word twice puts every rotation inside it as a normal substring: waterbottlewaterbottle contains erbottlewat. The length check stops false matches.

Same code works in Java810172125Basic features only, so nothing changes between versions.

/*
 * Problem : Process two words.
 * Input   : Two words separated by a space.
 * Output  : true or false.
 * Approach: Search in the doubled word.
 * Time    : O(n^2) worst case with simple search
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static boolean solve(String a, String b) {
        // Step 1: Words of different length cannot be rotations of each other.
        if (a.length() != b.length()) {
            return false;
        }

        // Step 2: Every rotation of a is a part of a + a. So we search b inside the doubled word.
        return (a + a).contains(b);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String a = scanner.next();
        String b = scanner.next();
        System.out.println(solve(a, b));
    }
}

Hints (1)

Which longer word contains all rotations?