Start learning free

LESSON 247 OF 675 · HELPER FUNCTIONS

Palindrome Words in TypeScript: A Helper and a Filter

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

    TYPESCRIPT · HELPER FUNCTIONS

    Palindrome Words in TypeScript, 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. If no word qualifies, the result is an empty array. Every word has 1 to 20 lowercase letters, and a word that appears more than once is kept each time.

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

    Approach: a helper for one word, a filter for many

    The work is split in two methods. The helper, isPalindrome, answers one question about one word: true or false. The graded method, palindromeWords, loops over the array, asks the helper about each word and keeps the ones for which the answer is true.

    The helper compares letters from both ends in a single loop. The first letter must equal the last, the second must equal the second to last, and so on. One mismatch is enough to answer false at once. If every pair matches, the word is a palindrome. Built-in functions that reverse the word are not allowed here; the loop does the comparing.

    Only half of the word has to be checked, because each turn of the loop checks two letters at the same time. Checking the second half would repeat the same pairs backwards.

    Step by step

    1. In isPalindrome, store the length of the word in n. The loop bound and the index of each partner letter both use it.
    2. Loop with i from 0 while i < n / 2. In TypeScript, n / 2 is not rounded, so for 5 letters it is 2.5 and i takes the values 0, 1 and 2. The last turn compares the middle letter with itself, which is harmless.
    3. Compare word[i] with word[n - 1 - i]. For i = 0 the partner is the last letter, at index n - 1. If the two differ, return false right away.
    4. Return true after the loop. No pair differed. A one-letter word has n / 2 = 0.5, so the loop body runs once for i = 0, compares the letter with itself and falls through to true.
    5. In palindromeWords, create palindromes, an empty string[].
    6. Loop over words with for (const word of words), which keeps the order.
    7. Call the helper as this.isPalindrome(word) inside the if. It already returns true or false, so it needs no comparison. When it is true, push word.
    8. Return palindromes after the loop. If nothing matched, it is still empty, which is the right answer.

    The solution in TypeScript

    class Solution {
    isPalindrome(word: string): boolean {
        let n: number = word.length;
        for (let i = 0; i < n / 2; i++) {
            if (word[i] !== word[n - 1 - i]) {
                return false;
            }
        }
        return true;
    }

    palindromeWords(words: string[]): string[] {
        let palindromes: string[] = [];
        for (const word of words) {
            if (this.isPalindrome(word)) {
                palindromes.push(word);
            }
        }
        return palindromes;
    }
}

    Details to notice:

    • Strings can be indexed. word[i] gives the character at position i as a one-character string, and !== compares two such strings by value.
    • Calling the helper needs this.. Inside a class, isPalindrome(word) alone refers to something outside the class.
    • Division is not integer division. 5 / 2 is 2.5. The loop works with that, because i < 2.5 stops after i = 2. Rounding down with Math.floor and writing i < Math.floor(n / 2) would also work, and would skip the middle letter.

    Tracing two words

    For "noon", n is 4, so i takes 0 and 1. At i = 0 the pair is n and n, equal. At i = 1 the pair is o and o, equal. The loop ends and the helper returns true.

    For "cat", n is 3 and the first pair, c and t, already differs, so the helper returns false without looking further. For "abcba", i takes 0, 1 and 2, and the pairs a/a, b/b and c/c all match, so the word is a palindrome.

    The shortcut the task rules out

    A palindrome equals its own reverse, so a one-line test exists: word === [...word].reverse().join(""). It gives true for "noon" and false for "cat". It builds a reversed copy of every word, which the two-ends loop never needs, and the task asks for the loop so that you practise working with indexes from both ends of a string.

    Edge cases and common mistakes

    • Returning true inside the loop. A matching first pair says nothing about the rest. Only the end of the loop proves the word is a palindrome.
    • Off-by-one partner. The partner of index i is n - 1 - i. Using n - i points one past the end for i = 0: "abc"[3] is undefined, and it would never equal a letter.
    • Comparing to the whole length. Looping while i < n still gives the right answer, because the second half repeats the first, but it does twice the work.
    • Returning inside the outer loop. A return in palindromeWords placed inside the for would stop after the first word.
    • Duplicates. The task keeps a palindrome every time it appears, and the loop does that naturally.

    Testing

    • ["pup", "cat", "noon", "dog"] gives ["pup", "noon"].
    • ["a", "bob", "abba", "ab"] gives ["a", "bob", "abba"].
    • ["kitten", "parrot"] gives [].
    • The helper alone: isPalindrome("abcba") is true and isPalindrome("ab") is false.
    Keep going with TypeScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free