Start learning free

LESSON 243 OF 671 · HELPER FUNCTIONS

Palindrome Words in Java: A Helper Method With Two Ends

Practice Read the full explanation

You get an array of words, words. Return the words that are palindromes, in the same order.

A palindrome reads the same from left to right and from right to left, like "noon". A word with one letter is a palindrome too. If no word is a palindrome, the result is empty.

The work is split between two functions. The first one is a helper. It gets one word and returns true if it is a palindrome, false if not. The second one is the function that is graded. It keeps the words for which the helper returns true.

The helper compares the letters from both ends of the word, in one loop. Don't use a built-in function that reverses the word.

 

Example 1:

Input: words = ["pup", "cat", "noon", "dog"]
Output: ["pup", "noon"]
Explanation: The words "pup" and "noon" read the same both ways.
Read backwards, "cat" is "tac".
Read backwards, "dog" is "god".

Example 2:

Input: words = ["a", "bob", "abba", "ab"]
Output: ["a", "bob", "abba"]
Explanation: The word "a" has one letter, so it is a palindrome.
Read backwards, "ab" is "ba".

Example 3:

Input: words = ["kitten", "parrot"]
Output: []
Explanation: No word reads the same both ways.

 

Constraints:

  • words has at least one word.
  • Every word has 1 to 20 lowercase letters.
  • A word can appear more than once. Each palindrome is kept every time it appears.
STEP 1 OF 8
    Ctrl + Enter to check

    JAVA · HELPER FUNCTIONS

    Palindrome Words in Java, explained

    Problem overview

    The method palindromeWords receives an array of words and returns the ones that are palindromes, in the same order. A palindrome reads the same from left to right and from right to left, like "noon". A word with one letter is a palindrome too. If no word is a palindrome, the result is empty. A palindrome that appears twice is kept twice.

    For ["pup", "cat", "noon", "dog"] the result is [pup, noon]. For ["a", "bob", "abba", "ab"] it is [a, bob, abba]. For ["kitten", "parrot"] it is [].

    Approach: a helper that checks one word

    The work is split in two methods. The helper isPalindrome decides about a single word. palindromeWords loops over the array and keeps the words for which the helper says true. The lesson asks you not to use a method that reverses the word. The helper compares the letters from both ends in one loop instead.

    The idea: the first letter must equal the last, the second must equal the second from the end, and so on. After checking half of the word, every letter has been compared with its partner. In a word of odd length, the middle letter has no partner and needs no check.

    Step by step

    1. In isPalindrome, store word.length() in an int named n.
    2. Write a for loop with i starting at 0, running while i < n / 2. Division of two ints drops the remainder, so for 5 letters n / 2 is 2.
    3. Inside the loop, compare word.charAt(i) with word.charAt(n - 1 - i). If they differ, return false at once. One bad pair is enough.
    4. After the loop, return true. A one-letter word skips the loop and gets here.
    5. In palindromeWords, create an empty List<String> named palindromes.
    6. Loop over words with a String named word.
    7. If isPalindrome(word) is true, add word to palindromes.
    8. After the loop, return palindromes.

    The solution in Java

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

    public List<String> palindromeWords(String[] words) {
        List<String> palindromes = new ArrayList<>();
        for (String word : words) {
            if (isPalindrome(word)) {
                palindromes.add(word);
            }
        }
        return palindromes;
    }
}

    Some Java details:

    • word.charAt(i) gives a char, and != compares two chars by value. That is different from strings, where you must use equals.
    • The partner of index i is n - 1 - i. For "noon", n is 4, so index 0 pairs with 3 and index 1 pairs with 2.
    • The call isPalindrome(word) already gives a boolean, so it goes straight into the if. Writing == true adds nothing.

    Following the helper on two words

    For "noon", n is 4 and the loop runs for i equal to 0 and 1. At i = 0 it compares the first n with the last n: equal. At i = 1 it compares o with o: equal. The loop ends and the helper returns true.

    For "cat", n is 3, so n / 2 is 1 and the loop runs once, for i = 0. It compares c with t, finds them different and returns false immediately. The a in the middle is never looked at.

    Why a helper is worth it

    The loop that compares the letters and the loop that goes over the words do different jobs. Keeping them in two methods means each loop has its own variables and its own return. In particular, the early return false in isPalindrome ends only the check of one word. If both loops lived in one method, that return would end the whole method, and you would need extra flags to carry on with the next word. As two methods, palindromeWords just asks a yes or no question once per word.

    Edge cases and common mistakes

    • Looping over the whole word. It still works, because each pair is compared twice, but it does double the work.
    • Using n - i as the partner. Indexes start at 0, so the last letter is at n - 1. n - i would go out of range at i = 0 and throw a StringIndexOutOfBoundsException.
    • Returning true inside the loop. One matching pair proves nothing. Only a different pair gives an early answer, and true comes after the loop.
    • Odd lengths. "abcba" has a middle letter c that is never compared, and that is correct.

    Case and the lesson's inputs

    The lesson promises that every word has 1 to 20 lowercase letters, so the helper doesn't need to deal with capitals, spaces or an empty word. The comparison is exact: 'a' and 'A' are different characters, so a word like "Noon" would not count as a palindrome with this code.

    Words that appear several times are kept every time. The loop calls the helper once per array item, so a repeated palindrome is added once for each appearance. Nothing in the method removes duplicates.

    Finding a bug

    If a non-palindrome is kept, look at the helper: the loop may stop too early (for example i < n / 2 - 1), so the last pair is never compared. If a palindrome is missing, the helper may return false too eagerly, such as comparing a letter with the wrong partner. If the order is wrong, look at palindromeWords.

    Testing

    Running the solution on the three examples gives:

    [pup, noon]
[a, bob, abba]
[]

    Calling isPalindrome alone on "abcba", "abca" and "a" gives true, false and true.

    Keep going with Java500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free