Recursive Palindrome

Lab Java Intermediate 20 points

Write a recursive static boolean isPal(String s, int lo, int hi). Print true or false for each input word.

Input

n, then n words.

Output

n lines.

Example

Input

4
level
java
a
abba

Output

true
false
true
true

Sample input available Sample output available

Editor

Java

Hints

Compare the outer characters, then recurse on the inside.

Solution explanation

&& short-circuits: the recursion stops at the first mismatch.

Show solution

import java.util.Scanner;

public class Main {
    static boolean isPal(String s, int lo, int hi) {
        if (lo >= hi) {
            return true;
        }
        return s.charAt(lo) == s.charAt(hi) && isPal(s, lo + 1, hi - 1);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            String w = sc.next();
            System.out.println(isPal(w, 0, w.length() - 1));
        }
    }
}

Output

Answer