Start learning free

LESSON 242 OF 667 · HELPER FUNCTIONS

Palindrome Words in C++: A Helper with Two-End Comparison

Practice Read the full explanation

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

Guided

Ctrl + Enter to check

C++ · HELPER FUNCTIONS

Palindrome Words in C++, explained

Problem overview

The function palindromeWords gets a vector of words and returns 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. A word that appears twice and is a palindrome is kept twice. If no word is a palindrome, the result is empty. Every word has 1 to 20 lowercase letters.

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 an empty vector. The tests print a vector as its words separated by spaces.

The work is split between two functions. The helper isPalindrome answers the question for one word. palindromeWords keeps the words for which the helper says true. The helper compares letters from both ends in one loop, without a function that reverses the word.

Approach

Compare the first letter with the last, the second with the second to last, and so on. The first pair that differs proves the word isn't a palindrome, so the helper returns false immediately. If no pair differs, the word is a palindrome.

Only half of the word needs checking, because each turn of the loop covers two letters. For n letters the loop runs while i < n / 2. Integer division drops the remainder, so a 5-letter word makes 2 comparisons and its middle letter, which has no partner, is never looked at. A 1-letter word makes 0 comparisons and goes straight to true.

The partner of index i is n - 1 - i. For i = 0 that is the last index, n - 1; for i = 1 it is the index before that.

Watching the pairs

Here are the pairs the loop compares for three words:

noon compares n with n, then o with o. No pair differs, so it is a palindrome.
cat compares c with t and stops at once. They differ, so the word is not a palindrome, and the a in the middle is never looked at.
abcba compares a with a and b with b. The middle c has no partner, and the word is a palindrome.

Step by step

In isPalindrome, store the length word.size() in an int named n.
Loop with i from 0 while i < n / 2.
Compare word[i] with word[n - 1 - i]. If they differ, return false right away.
After the loop, return true. No pair differed.
In palindromeWords, start with an empty vector<string> named palindromes.
Loop over words with a string named word. Going from first to last keeps the order.
If isPalindrome(word) is true, add the word with push_back. The helper's answer is already a bool, so it goes straight into the if.
Return palindromes after the loop. It stays empty if nothing matched.

The solution in C++

class Solution {
public:
    bool isPalindrome(string word) {
        int n = word.size();
        for (int i = 0; i < n / 2; i++) {
            if (word[i] != word[n - 1 - i]) {
                return false;
            }
        }
        return true;
    }

    vector<string> palindromeWords(vector<string> &words) {
        vector<string> palindromes;
        for (string word : words) {
            if (isPalindrome(word)) {
                palindromes.push_back(word);
            }
        }
        return palindromes;
    }
};

Notes on the C++:

word.size() is unsigned. Storing it in an int first keeps n - 1 - i a normal signed calculation. With an unsigned n, a subtraction that goes below zero would wrap around to a huge number.
word[i] is a char, and != compares two characters by value.
The helper takes the word by value, so it works on a copy. The words here are at most 20 letters long.

Why the helper returns early

The helper is a yes or no question, and a single wrong pair answers it. Returning at that moment saves the remaining comparisons, and it keeps the code short: there is no flag to set and no extra variable. The return true after the loop is only reached when the loop ended without finding a mismatch.

Complexity

The helper makes at most half as many comparisons as the word has letters, and it often stops sooner. The main function calls it once per word, so the total work is proportional to the total number of letters in all the words. The result vector holds at most one copy of each input word.

Edge cases and common mistakes

One-letter words. "a" skips the loop and returns true.
Odd lengths. "abcba" makes two comparisons, and the middle c is left alone.
Looping to n. It still gives correct answers, since the second half repeats the first half's comparisons, but it does twice the work.
Off-by-one on the partner. word[n - i] is out of range for i = 0. The partner is n - 1 - i.
Returning true inside the loop. A matching pair proves nothing about the other pairs. Only a mismatch can decide early.
Dropping duplicates. A repeated palindrome is kept every time; the code never removes anything.

Testing

{"pup", "cat", "noon", "dog"} gives pup noon.
{"a", "bob", "abba", "ab"} gives a bob abba.
{"kitten", "parrot"} gives an empty vector.
For the helper alone, isPalindrome("a") is true, isPalindrome("ab") is false and isPalindrome("abcba") is true.

Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free