Problem overview
The method palindromeWords gets an array 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 word with one letter is a palindrome too. A word that appears more than once is kept every time it appears, and if no word is a palindrome the result is an empty array.
For ["pup", "cat", "noon", "dog"] the answer is ["pup", "noon"]. For ["a", "bob", "abba", "ab"] the answer is ["a", "bob", "abba"]. For ["kitten", "parrot"] the answer is empty.
Approach: a helper for one word
The work is split in two. The helper isPalindrome answers one question about one word: true or false. 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. If any pair differs, the word is not a palindrome. If no pair differs, it is. Only half of the word needs checking, because the second half repeats the same pairs. The lesson asks for this one-loop comparison, so the word is never reversed.
Step by step
- In
isPalindrome, store the length of the word innwithlet n = word.length. The loop and the partner index both need it. - Loop over the first half:
for (let i = 0; i < n / 2; i++). Each turn compares one letter from the front with one from the back. - Compare with the partner. The partner of
word[i]isword[n - 1 - i]: fori = 0it is the last letter, fori = 1the one before it. If the two differ, returnfalseright away. - Return
trueafter the loop. No pair was different. A one-letter word runs the loop once, fori = 0, where the letter is compared with itself, and gets here too. - In
palindromeWords, start with an empty array namedpalindromes. - Loop over the words with
for (let word of words), first to last, so the order is kept. - Call the helper inside an
if:this.isPalindrome(word)is alreadytrueorfalse, so it goes straight into the condition. Pushwordwhen it is true. - Return
palindromesafter the loop.
The solution in JavaScript
class Solution {
isPalindrome(word) {
let n = word.length;
for (let i = 0; i < n / 2; i++) {
if (word[i] != word[n - 1 - i]) {
return false;
}
}
return true;
}
palindromeWords(words) {
let palindromes = [];
for (let word of words) {
if (this.isPalindrome(word)) {
palindromes.push(word);
}
}
return palindromes;
}
}
Some details worth a look:
- Dividing by 2 gives a fraction. In JavaScript,
5 / 2is 2.5, not 2. The loop conditioni < n / 2still works: for 5 letters,itakes the values 0, 1 and 2, and 2 is the middle letter, which is compared with itself. That is harmless. For 4 letters,iis 0 and 1. - Indexing a string.
word[i]gives a one-character string, and!=compares two such strings by content. - Calling the helper. Inside the class, use
this.isPalindrome(word).
Following two words
For "noon", n is 4 and the loop runs for i = 0 and i = 1. At i = 0 the helper compares word[0], "n", with word[3], "n": equal. At i = 1 it compares word[1], "o", with word[2], "o": equal. The loop ends and the helper returns true.
For "cat", n is 3. At i = 0 it compares "c" with word[2], "t". They differ, so the helper returns false at once, without looking at the rest. Stopping at the first mismatch is why the helper has two different return statements: one inside the loop for a mismatch, one after it for a word whose pairs all matched.
Testing
The helper on single words returns true for "noon", false for "cat", true for "a" and true for "level". On the statement's examples, the lesson's solution prints these lines, with an empty line for the last example:
pup noon
a bob abba
A word with five letters, such as "level", is checked with i equal to 0, 1 and 2, because the loop runs while i < 2.5; the helper returns true for it. The word "abca" fails on the second pair, where b meets c.
Common mistakes
- Returning
trueinside the loop. A match between one pair says nothing about the other pairs. If the loop returnstrueon the first matching pair, "abca" givestrue, and so do "cat" and "dog", because their middle letter matches itself. Returnfalseon a mismatch, andtrueonly after the loop. - Looping to
ninstead of half. It still gives the right answer, because the second half repeats the same pairs, but it does twice the work. - Forgetting the
- 1. The last letter is at indexn - 1.word[n - i]starts atword[n], which isundefined, so the first comparison fails and every word, even "a", looks like it is not a palindrome. - Dropping duplicates. A palindrome that appears twice is kept twice. The loop visits it twice, so it is pushed twice.
