Java Basics Practical - Palindromes

exercises
lab
java
strings
recursion

Practical exercises for week 2. IntelliJ IDEA is the course’s supported IDE (see the install guide on Blackboard). The Java 21 API docs cover the String class in java.lang, which is needed below.

On the HTML site, fill in each blank with your answer (as a quoted string, e.g. "true"), then click Run Code to check it. In the PDF, the Working callout is shown as a static answer key instead (interactive checking needs a browser).

Question 1 — Palindromes

A palindrome reads the same forwards and backwards, e.g. "AaaA", "madamimadam", "racecar".

Implement four methods, all with the signature public static boolean isPalindromeN(String word) (for \(N=1..4\)), each using a different technique:

  1. isPalindrome1 — a for loop.
  2. isPalindrome2 — a while loop.
  3. isPalindrome3 — recursive, with no helper methods.
  4. isPalindrome4 — recursive, using a private helper method.

All four should agree on at least these cases. What does each return?

isPalindromeN("AaA") →

isPalindromeN("A") →

isPalindromeN("") →

isPalindromeN("Abbb") →

All four methods do the same comparisons — first character against last, second against second-last, and so on — but they keep track of where they are up to in two structurally different ways:

Figure 1: The two reductions behind the four methods. (a) isPalindrome1, isPalindrome2 and isPalindrome4 leave the string alone and move an index i inwards, comparing charAt(i) with charAt(len - i - 1) and stopping once i reaches len / 2 - which is why the middle character of an odd-length word is never examined. (b) isPalindrome3 keeps no index at all: it compares the two ends, then recurses on substring(1, length() - 1), so the string itself shrinks by two characters per call until length() < 2 is the base case. Characters no longer in the live window are greyed out; the teal double arrows are comparisons.

Task 0 — isPalindrome1 (for loop):

public static boolean isPalindrome1(String word) {
    int len = word.length();
    for (int i = 0; i < len / 2; i++) {
        if (word.charAt(i) != word.charAt(len - i - 1)) {
            return false;
        }
    }
    return true;
}

Task 1 — isPalindrome2 (while loop):

public static boolean isPalindrome2(String word) {
    int len = word.length();
    int i = 0;
    while (i < len / 2) {
        if (word.charAt(i) != word.charAt(len - i - 1)) {
            return false;
        }
        i++;
    }
    return true;
}

Task 2 — isPalindrome3 (recursive, no helper methods). To write any recursive method, identify the base case (the input is trivially solvable — obviously a palindrome or obviously not) and the recursive case (which must reduce the problem to a smaller one, moving towards the base case). Applied here: if \(xy \ldots yx\) is a palindrome, then \(y \ldots y\) must be too — and substring is how you extract \(y \ldots y\) (panel (b) of Figure 1).

public static boolean isPalindrome3(String word) {
    if (word.length() < 2) {
        return true; // base case
    }
    if (word.charAt(0) != word.charAt(word.length() - 1)) {
        return false; // base case
    }
    return isPalindrome3(word.substring(1, word.length() - 1)); // recursive step
}

Task 3 — isPalindrome4 (recursive, with a private helper). The helper carries the index, so this is panel (a)’s reduction driven by recursion rather than by a loop. Because the index does the work, this version never calls substring, so unlike isPalindrome3 it allocates no new String on each step.

public static boolean isPalindrome4(String word) {
    return helper(word, 0);
}

private static boolean helper(String word, int i) {
    if (i >= word.length() / 2) {
        return true; // base case
    }
    if (word.charAt(i) != word.charAt(word.length() - i - 1)) {
        return false; // base case
    }
    return helper(word, i + 1); // recursive step
}

All four agree on the required test cases: "AaA" → true, "A" → true, "" → true, "Abbb" → false.

Code review

A paired activity, not a gradable exercise: swap solutions with a partner, and for each other’s code —

  • Understand it, and ask questions about anything unclear.
  • Check correctness against the test cases above (and a few of your own).
  • Check it follows the course style guide.
  • Discuss/suggest improvements if you find issues.

Then discuss which of the four isPalindromeN techniques you each preferred, and why.