Start learning free

LESSON 243 OF 673 · HELPER FUNCTIONS

Palindrome Words in Python: Two Pointers in a Helper

Practice Read the full explanation

You get a list 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

    PYTHON · HELPER FUNCTIONS

    Palindrome Words in Python, explained

    Problem overview

    The method palindromeWords receives a list of lowercase 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 one-letter word is a palindrome. A word that appears twice is kept twice, and if no word qualifies the result is an empty list.

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

    Approach: a helper for one word

    The work is split in two. The helper isPalindrome answers a single question about a single word. palindromeWords then loops over the list and keeps each word for which the helper says True.

    To test one word, compare letters in pairs from both ends: the first with the last, the second with the second to last, and so on. One mismatched pair proves the word is not a palindrome. If every pair matches, it is. Only the first half of the word needs to be visited, because each step checks two letters.

    The task asks for this loop and not for a built-in way to reverse the word.

    Step by step

    1. In isPalindrome, store n = len(word).
    2. Loop with for i in range(n // 2). For 4 letters that is i = 0 and 1; for 5 letters it is 0 and 1 too, since the middle letter needs no partner; for 1 letter it is no turns at all.
    3. Compare word[i] with word[n - 1 - i]. For i = 0 the partner is the last letter, at index n - 1. If they differ, return False at once.
    4. After the loop, return True.
    5. In palindromeWords, start with an empty list palindromes.
    6. Loop with for word in words, and if self.isPalindrome(word) is true, append word.
    7. After the loop, return palindromes.

    The solution in Python

    class Solution:
    def isPalindrome(self, word: str) -> bool:
        n = len(word)
        for i in range(n // 2):
            if word[i] != word[n - 1 - i]:
                return False
        return True

    def palindromeWords(self, words: List[str]) -> List[str]:
        palindromes = []
        for word in words:
            if self.isPalindrome(word):
                palindromes.append(word)
        return palindromes

    Notes:

    • // is whole-number division. range(5 // 2) is range(2), and range(1 // 2) is empty.
    • For "noon" the pairs are n with n and o with o, both equal, so the helper returns True. For "cat" the only pair is c with t, which differ, so it returns False on the first turn.
    • The helper's result is already True or False, so the call goes straight into the if.

    Why the helper helps

    The pair-comparing loop is the harder part. Keeping it in its own method means palindromeWords reads almost like the task itself: for each word, if it is a palindrome, keep it. You can also test the helper alone: isPalindrome("racecar") is True and isPalindrome("abca") is False (the outer pair matches, but the inner pair, b and c, does not).

    Testing

    wordsresult
    ["pup", "cat", "noon", "dog"]["pup", "noon"]
    ["a", "bob", "abba", "ab"]["a", "bob", "abba"]
    ["kitten", "parrot"][]

    Common mistakes

    • Looping over the whole word. It does twice the work, and gives the same answer.
    • Using word[n - i]. The last index is n - 1, so word[n - 0] is out of range and raises IndexError.
    • Returning True inside the loop after the first matching pair. One match proves nothing; only a mismatch is conclusive.
    • Dropping the final return True. A palindrome would then return None, which counts as false.
    Keep going with Python500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free