Problem overview
The method palindromeWords gets an Array[String] called words and returns the words that are palindromes, in the same order, as an ArrayBuffer[String]. 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 palindrome that appears twice is kept twice, and if there are none the result is empty.
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.
Approach
The work is split between two methods. The helper isPalindrome looks at one word and answers true or false. palindromeWords calls it on every word and keeps the ones that pass. The helper does not reverse the word. It compares the first letter with the last, the second with the one before the last, and so on. One loop over half of the word is enough.
Why compare pairs
Think of two fingers, one on the first letter and one on the last. If the letters under them differ, the word cannot be a palindrome. If they match, move both fingers one step inwards and compare again. When the fingers meet or cross, every pair has matched. The loop counter i is the left finger, and n - 1 - i is the right finger, always the same distance from the other end.
Step by step
The helper
- Store
word.lengthinn, aval. - Loop with
for (i <- 0 until n / 2). Each turn checks two letters, so half the word is enough. For 5 letters,n / 2is 2 (integer division drops the remainder), and the middle letter needs no partner. - Compare
word(i)with its partner from the end,word(n - 1 - i). If they differ, returnfalseat once: one different pair is enough. - After the loop, return
true. A one-letter word skips the loop and gets here.
The main method
- Create an empty
ArrayBuffer[String]calledpalindromes. - Loop with
for (word <- words), from the first word to the last, so the order is kept. - If
isPalindrome(word)is true, append the word with+=. The helper's answer is alreadytrueorfalse, so the call goes straight into theif. - Return
palindromes.
The solution in Scala
class Solution {
def isPalindrome(word: String): Boolean = {
val n = word.length
for (i <- 0 until n / 2) {
if (word(i) != word(n - 1 - i)) {
return false
}
}
return true
}
def palindromeWords(words: Array[String]): ArrayBuffer[String] = {
val palindromes = ArrayBuffer[String]()
for (word <- words) {
if (isPalindrome(word)) {
palindromes += word
}
}
return palindromes
}
}
In Scala a string is indexed with parentheses, word(i), not square brackets. The range 0 until n / 2 stops before n / 2, so for "abba" it gives the indices 0 and 1, which pair with 3 and 2.
The comparisons for two words
For "abba" the loop makes two comparisons, a with a and b with b, both equal, so the helper returns true. For "abca" the first pair matches (a and a), the second does not (b and c), and the helper returns false there, without looking further.
Duplicates and order
The main method never looks at what it already kept, so a palindrome that appears twice is appended twice. That is what the statement asks for. The loop also visits the words from first to last and appends at the end of the buffer, so the kept words come out in their original order without any sorting. When no word passes, nothing is appended and the empty buffer is returned, which is the correct answer.
Inside the helper, word(i) and word(n - 1 - i) are single characters, and != compares their values. The early return false leaves the helper at once, in the middle of the loop, so the remaining pairs are not checked.
Testing
The three examples return pup noon, a bob abba and an empty buffer (the tests print lists as values separated by spaces). The helper alone says isPalindrome("abcba") is true and isPalindrome("abca") is false.
Another way
Two indexes that move towards each other do the same job as the loop over half the word:
def isPalindrome(word: String): Boolean = {
var left = 0
var right = word.length - 1
while (left < right) {
if (word(left) != word(right)) return false
left += 1
right -= 1
}
true
}
On pup, cat, noon, dog and a it returns true, false, true, false, true. It is the "two fingers" picture written literally. The lesson's version needs one variable fewer and cannot get the stopping condition wrong, since the loop count is fixed in advance.
The library also offers word == word.reverse, which gives true for "noon". This lesson asks for the comparison loop instead, so that you practise indexes and early exits.
Edge cases and common mistakes
- Odd length. The middle letter is its own partner, so the loop stops before it.
n / 2does that. - Looping over the whole word. It gives the same answer but checks every pair twice.
- Returning
trueinside the loop. One matching pair proves nothing. The helper returnstrueonly after all pairs have matched. - Off-by-one partner index. The last letter is at
n - 1, notn. Asking forword(n)throws aStringIndexOutOfBoundsException, so the partner of indexiisword(n - 1 - i). - Reversing the word is not allowed here, and the two-ended comparison needs no extra string.
