Start learning free

LESSON 246 OF 674 · HELPER FUNCTIONS

Palindrome Words in C#: A Helper That Compares Both 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

    C# · HELPER FUNCTIONS

    Palindrome Words in C#, explained

    Problem overview

    You get a string[] named words. PalindromeWords returns the words that read the same from left to right and from right to left, in the same order, as a List<string>. A word with one letter counts as a palindrome. 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"], and for ["kitten", "parrot"] it is empty. A word that appears twice is kept each time.

    Approach

    The work is split in two. The helper IsPalindrome answers the question for one word. PalindromeWords loops over the array and keeps the words for which the helper says true.

    The helper compares letters in pairs from both ends: the first with the last, the second with the second to last, and so on. One pair that differs settles it: the word is not a palindrome. If every pair matches, it is. Only half of the word needs to be checked, because the second half is the same pairs seen from the other side. The middle letter of an odd-length word has no partner and needs no check.

    Step by step

    1. In IsPalindrome, store word.Length in n. Both the loop limit and the partner's index use it.
    2. Loop with for (int i = 0; i < n / 2; i++). Integer division drops the remainder, so a 5-letter word gives 2 pairs and a 1-letter word gives none.
    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. Return true after the loop. 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 foreach, from the first word to the last, so the order is kept.
    7. If IsPalindrome(word) is true, add the word. The call returns a bool, so it goes straight into the if.
    8. Return palindromes.

    The solution in C#

    class Solution {
    public bool IsPalindrome(string word) {
        int n = word.Length;
        for (int i = 0; i < n / 2; i++) {
            if (word[i] != word[n - 1 - i]) {
                return false;
            }
        }
        return true;
    }
    public List<string> PalindromeWords(string[] words) {
        List<string> palindromes = new List<string>();
        foreach (string word in words) {
            if (IsPalindrome(word)) {
                palindromes.Add(word);
            }
        }
        return palindromes;
    }
}

    The details worth knowing:

    • A string is indexed like an array, word[i], and gives a char. Strings are immutable, so you can read characters but not assign to them.
    • The length of a string is the property Length, with no parentheses.
    • Comparing two char values with != compares the characters themselves.

    Watching the pairs

    For "noon" the length is 4, so the loop makes two comparisons. The first compares the outer letters and the second the inner ones:

    i=0: n vs n
i=1: o vs o

    Both pairs match, so the loop ends and the method returns true. For "abca" the first pair is fine but the second is not:

    i=0: a vs a
i=1: b vs c

    At i = 1 the letters differ, so the method returns false without looking further. The same idea works with two index variables that start at both ends and move toward each other (while (i < j), then i++ and j--). That version gives the same answers on these words. The lesson's for version needs only one variable, because the partner's index follows from i and n.

    Why the helper stays separate

    The helper has its own loop, and PalindromeWords has another one. Keeping them apart means that neither loop has to deal with the other's variables: the helper thinks in letters and indexes, the outer method thinks in words. In the outer loop there is nothing to compute, only a question to ask once per word.

    Testing

    The helper gives these answers for a few small words:

    a True
ab False
aba True
abca False

    On the statement's three examples, PalindromeWords returns:

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

    Here the lists are printed with their values separated by commas; the lesson's tests print them with spaces.

    Edge cases and common mistakes

    • Using word[n - i] as the partner. At i = 0 that is index n, one past the last letter, and C# throws an IndexOutOfRangeException. The partner of index i is n - 1 - i.
    • Returning true inside the loop. One matching pair proves nothing. Only a mismatch can end the check early.
    • Treating a one-letter word as a special case. It needs none: 1 / 2 is 0, so the loop doesn't run and the method returns true.
    • Reversing the word. The lesson asks for the one-loop comparison from both ends.

    Checking your own version

    Test the helper on its own first. Good inputs are a one-letter word, a two-letter word that matches ("aa"), a two-letter word that doesn't ("ab"), an odd-length palindrome and an even-length one. Those cases catch the usual off-by-one slips in the loop limit and in the partner index.

    Then run the full method on a list with a repeated palindrome. A word that appears twice must be kept twice, because the loop simply asks the helper about each word as it comes. The method never needs to remember which words it has already seen.

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