/******************************************************************************
 * This program compares recursion to iteration in computing palindromes.
 * 
 * Copyright © 2021 Richard Lesh.  All rights reserved.
 *****************************************************************************/

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.regex.Pattern;
import org.pureprogrammer.Utils;

public class Palindrome {

    static final List<String> TEST_CASES = Utils.listFromStrings(new String[]{"Hannah", "Able was I ere I saw Elba", "A man, a plan, a canal – Panama", "T. Eliot, top bard, notes putrid tang emanating, is sad; I'd assign it a name: gnat dirt upset on drab pot toilet.", "This is not a palindrome!"});

    static boolean palindromeRecursive0(String s) {
        final int S_LEN = Utils.cpLength(s);
        if (S_LEN < 2) {
            return true;
        }
        if (Utils.cpAt(s, 0) != Utils.cpAt(s, S_LEN - 1)) {
            return false;
        }
        return palindromeRecursive0(Utils.cpSubstring(s, 1, (S_LEN - 1)));
    }

    static boolean palindromeRecursive(String s) {
        String s0 = Pattern.compile("\\W+").matcher(s).replaceAll("");
        s0 = s0.toLowerCase();
        return palindromeRecursive0(s0);
    }

    static boolean palindromeIterative(String s) {
        String s0 = Pattern.compile("\\W+").matcher(s).replaceAll("");
        s0 = s0.toLowerCase();
        final int S_LEN = Utils.cpLength(s0);
        for (int x = 0; x <= (S_LEN - 1) / 2; ++x) {
            if (Utils.cpAt(s0, x) != Utils.cpAt(s0, S_LEN - 1 - x)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        for (String s : TEST_CASES) {
            System.out.println(Utils.join("", "Test Case: ", s));
            boolean result = palindromeRecursive(s);
            System.out.println(Utils.join("", "palindromeRecursive: ", (result ? "Yes" : "No")));
            result = palindromeIterative(s);
            System.out.println(Utils.join("", "palindromeIterative: ", (result ? "Yes" : "No")));
        }
    }
}