Problem overview
The function palindromeWords gets 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 one-letter word is a palindrome. A word that appears twice and is a palindrome is kept both times. 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"], and for ["kitten", "parrot"] it is empty.
The work is split in two. The helper isPalindrome gets one word and returns true or false. palindromeWords is the function the tests call, and it keeps the words for which the helper says true. The helper compares letters from both ends in one loop, without a built-in function that reverses the word.
Approach for the helper
Compare the first letter with the last, the second with the second to last, and so on. The word is a palindrome if every pair matches. You only need to check half of the word: after that, the pairs repeat. For a word of length n, the pair of index i is index n - 1 - i. For "noon", n is 4, so the pairs are index 0 with 3 and index 1 with 2. The loop is for (i in 0 until n / 2).
The integer division n / 2 drops the remainder. For a word with 5 letters it is 2, so the middle letter is never compared, which is right: it is its own partner. For a one-letter word, n / 2 is 0, the loop never runs, and the word counts as a palindrome.
Step by step
- In
isPalindrome, storeword.lengthin aval n. - Loop
iover0 until n / 2. The range0 until kgoes from 0 tok - 1. - If
word[i]differs fromword[n - 1 - i], returnfalseat once. One bad pair is enough. - After the loop, return
true: no pair was different. - In
palindromeWords, create an emptymutableListOf<String>()namedpalindromes. - Loop over
words. IfisPalindrome(word), add the word to the list. The call is already aBoolean, so it goes straight into theif. - Return
palindromesafter the loop.
The solution in Kotlin
class Solution {
fun isPalindrome(word: String): Boolean {
val n = word.length
for (i in 0 until n / 2) {
if (word[i] != word[n - 1 - i]) {
return false
}
}
return true
}
fun palindromeWords(words: Array<String>): List<String> {
val palindromes = mutableListOf<String>()
for (word in words) {
if (isPalindrome(word)) {
palindromes.add(word)
}
}
return palindromes
}
}
In Kotlin, word[i] gives the Char at index i, and != compares the two characters by value. The helper gives true for "noon", "a" and "level", and false for "cat". The tests print lists as values separated by spaces, so the examples print:
pup noon
a bob abba
The third example has no palindromes, so nothing is printed.
Following the helper
Here are the comparisons the helper makes for a few words. For "noon" it compares n with n and then o with o, and returns true. For "level" it compares l with l and e with e; the middle v is never compared, and the result is true. For "abca" it compares a with a, which matches, and then b with c, which does not, so it returns false before looking at anything else. For "a" there are no comparisons and the result is true.
Because the helper stops at the first mismatch, it often does far less than the full half of the word.
Kotlin details
A few things in this code are specific to Kotlin:
0 until n / 2is a range that stops beforen / 2. Withn = 4the values ofiare 0 and 1. The range0..n / 2would include the end, which is one pair too many for even lengths.- The input type is
Array<String>, andfor (word in words)loops over it directly. - The result is built in a
MutableListheld in aval. The variable always points to the same list, and the list grows. - Comparing
word[i]withword[n - 1 - i]compares twoCharvalues, so!=checks their contents.
Complexity
For a word of length n the helper makes at most n / 2 comparisons. palindromeWords calls it once per word, so the total work is proportional to the combined length of all the words. The result list holds at most as many words as the input.
Common mistakes
- Returning
trueon the first matching pair. Reversing the condition so it returnstruewhen two letters are equal makes"abca"a palindrome, which it is not. The rule is to returnfalseon the first mismatch, andtrueonly after all the pairs. - Using
n / 2wrongly. Looping ton - 1instead of stopping at the half compares the pairs again from the other side; it still gives the right answer for this task, but every pair is compared twice. - Off-by-one in the partner index. The partner of index
iisn - 1 - i, notn - i, which goes past the end of the word and throws aStringIndexOutOfBoundsException. - Dropping duplicates. The words are visited in order and each is tested alone, so a palindrome that appears twice is kept twice.
