Problem overview
palindromeWords receives a slice 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 is kept twice, and when no word qualifies the result is empty.
For ["pup", "cat", "noon", "dog"] the answer is [pup noon]. For ["a", "bob", "abba", "ab"] it is [a bob abba]. For ["kitten", "parrot"] it is [].
Approach
The work is split between a helper, isPalindrome, which answers the question for one word, and palindromeWords, which keeps the words for which the helper says true.
The helper compares letters from both ends in one loop: the first with the last, the second with the second to last, and so on. One mismatched pair settles the answer at once. Only half the word needs checking, because the second half would repeat the same pairs.
Step by step
The helper isPalindrome(word):
- Store
n := len(word). - Loop with
ifrom 0 whilei < n / 2. Integer division drops the remainder: for 5 letters,n / 2is 2, and the middle letter has no partner to compare with. - Compare
word[i]withword[n - 1 - i]. Fori = 0the partner is the last letter, at indexn - 1. If they differ, returnfalseimmediately. - After the loop, return
true. A one-letter word hasn / 2 = 0, skips the loop and arrives here.
The function palindromeWords(words):
- Create
palindromes := []string{}. - Loop with
for _, word := range words, which keeps the original order. - If
isPalindrome(word), append the word and assign the slice back. - Return
palindromesafter the loop.
The solution in Go
func isPalindrome(word string) bool {
n := len(word)
for i := 0; i < n / 2; i++ {
if word[i] != word[n - 1 - i] {
return false
}
}
return true
}
func palindromeWords(words []string) []string {
palindromes := []string{}
for _, word := range words {
if isPalindrome(word) {
palindromes = append(palindromes, word)
}
}
return palindromes
}
In Go, len(word) counts bytes and word[i] is a byte. That is exactly right for this lesson, whose words are lowercase English letters. For text with accented letters, a byte-by-byte comparison would not compare characters; you would convert to []rune first.
The helper's result is already a bool, so the call goes straight into the if.
Tracing the comparisons
Take "noon", so n is 4 and the loop runs for i = 0 and i = 1. Printing i, the two letters and whether they are equal gives:
0 n n true
1 o o true
Both pairs match, the loop ends, and the helper returns true. For "abca" the same printout is 0 a a true and then 1 b c false: the first pair matches, but at i = 1 the letters differ, so the helper returns false right there. It never needs to look further.
Why a helper
Checking one word is a complete small task of its own, with its own loop and its own early return. Putting it in a helper keeps palindromeWords short, so its loop only has to decide which words to keep. It also means the helper can be tried on single words before it is used on a whole slice.
The early return false inside the helper's loop is safe because it leaves only the helper. The loop in palindromeWords goes on to the next word.
The empty result
The result starts as []string{}, an empty slice with no elements, and stays that way if nothing is appended. The statement expects an empty result in that case, and the lesson's tests treat it as [].
Bytes and letters
Because strings in Go are sequences of bytes, comparing word[i] with word[n - 1 - i] compares bytes. For plain English letters each letter is one byte, so the helper is right. A letter such as é takes two bytes in UTF-8, so the word "été" has 5 bytes but 3 letters, and the byte-by-byte helper reports false for it even though it reads the same both ways. Converting the word with []rune(word) first and comparing runes fixes that, and with it the same word gives true. The lesson's words are all lowercase English letters, so the simple version passes.
Testing
[pup cat noon dog] -> [pup noon]
[a bob abba ab] -> [a bob abba]
[kitten parrot] -> []
Edge cases
Odd and even lengths both work. In "abcba", n / 2 is 2, so the pairs checked are the two outer ones, and the middle letter c is left alone because it is its own partner. In "abba" the loop checks the outer pair and then the inner pair. A word with two equal letters like "aa" passes on its single pair, and a word with two different letters like "ab" fails on it. Repeated words are kept every time, because the loop treats each element on its own.
Common mistakes
- Looping to
ninstead ofn / 2. The result stays correct but does double the work. - Using
n - ifor the partner. It is off by one and indexes past the end of the string, which panics. The partner isn - 1 - i. - Returning
trueinside the loop after one matching pair. Every pair must match, sotruecomes after the loop.
