// This applications reads input from the user, and determines whether the
// input is a palindrome. Only letters and digits are considered to be part
// of the string; other characters will be ignored. Case is also ignored, so
// "Aba" is considered to be a palindrome.
// The empty string is also considered to be a palindrome.
//
// File: Palindrome.java
// Author: Benjamin Lewis
// Last modified: Tuesday February 23, 1999
 

import java.io.*; 

public class Palindrome
{
  public static void main(String[] args)
  {
    String input = "";
    BufferedReader instream = 
         new BufferedReader(new InputStreamReader(System.in));

    System.out.println("Please input a string to be tested");
    System.out.print("> ");    // cute prompt
    try
    {
      input = instream.readLine();
    }
    catch (IOException e)
    {
      System.err.println("Uh oh, an IO exception occured: "+e.getMessage());
      System.exit(0);
    }
    if (isPalindrome(input))
    {
      System.out.println("The string \""+input+"\" is a palindrome.");
    }
    else
    {
      System.out.println("The string \""+input+"\" is not a palindrome.");
    }
  }

  public static boolean isPalindrome(String str)
  {
    // remove invalid (not letter or digit) chars from the outsides
    // of the string
    String stripped = stripOutsideInvalidChars(str);
    
    int first = 0;                   // first index of the string
    int last  = stripped.length()-1; // last index of the string
    char firstChar;                  // first (valid) char in the string
    char lastChar;                   // last (valid) char in the string

    if (stripped.length()<2)
    {
      // base case: any string of fewer than 2 chars is a palindrome
      return true; 
    }
    else 
    {
      firstChar = Character.toLowerCase(stripped.charAt(first));
      lastChar  = Character.toLowerCase(stripped.charAt(last));
      if (firstChar == lastChar)
      {
	// recursive case: if the first and last chars are the same
	// and the rest of the string is a palindrome, then the whole
	// string is a palindrome.
	// n.b. substring(i,j) method goes from i to j-1
	return isPalindrome(stripped.substring(first+1, last));
      }
      else
      {
	// first and last chars differ, so string is not a palindrome
	return false;
      }
    }
  }

  private static String stripOutsideInvalidChars(String str)
  {
    // returns a string with invalid (not letter or digit) chars at the
    // beginning and end of str removed
    
    int i = 0;
    int j = str.length()-1;
    boolean iValid;
    boolean jValid;
    boolean done = false;

    // increment i and decrement j until each indexes a valid character, or
    // there are no valid characters to be found.
    while (i<j && !done)
    {
      iValid = Character.isLetterOrDigit(str.charAt(i));
      jValid = Character.isLetterOrDigit(str.charAt(j));
      if (iValid && jValid)
      {
	done = true;
      }
      else
      {
	if (!iValid) i++;
	if (!jValid) j--; 
      }
    }
    if (i<=j)
    {
      return str.substring(i,j+1);
    }
    else
    {
      // return the empty string
      return "";
    }
  }
}