Problem overview
This lesson has two functions. The helper is_palindrome receives one word and returns true if it reads the same from left to right and from right to left, like "noon". A word with one letter is a palindrome too. The function that is tested, palindrome_words, receives a vector of words and returns the palindromes among them, in the same order. If a palindrome appears twice, it is kept twice. If none is a palindrome, the result is empty. The helper must compare letters from both ends in one loop and may not reverse the word with a built-in.
For ["pup", "cat", "noon", "dog"] the answer is ["pup", "noon"]. For ["a", "bob", "abba", "ab"] it is ["a", "bob", "abba"].
Approach
To test one word, compare its first letter with its last, its second with its second to last, and so on. If any pair differs, the word is not a palindrome. Only the first half needs checking, because every pair has one letter in each half. The middle letter of an odd-length word has no partner and needs no check. Then palindrome_words is a loop that keeps the words for which the helper says true.
Step by step
- In
is_palindrome, collect the letters into aVec<char>withword.chars().collect(). A Rust string can't be read with a number index; a vector of its characters can. - Store the count,
letters.len(), inn. It is ausize, the type Rust uses for lengths and indexes. - Loop
iover0..n / 2. The division drops the remainder, so for 5 letters the loop runs for 0 and 1, and the middle letter is skipped. - Compare
letters[i]withletters[n - 1 - i]. Fori = 0the partner is the last letter. If they differ, returnfalseat once. - After the loop, return
true. No pair differed. A one-letter word skips the loop, since1 / 2is 0, and gets here too. - In
palindrome_words, create an empty mutable vectorpalindromes, loop overwords, and push each word for whichSelf::is_palindrome(&word)is true. Return the vector.
The solution in Rust
impl Solution {
fn is_palindrome(word: &str) -> bool {
let letters: Vec<char> = word.chars().collect();
let n = letters.len();
for i in 0..n / 2 {
if letters[i] != letters[n - 1 - i] {
return false;
}
}
return true;
}
fn palindrome_words(words: Vec<String>) -> Vec<String> {
let mut palindromes = Vec::new();
for word in words {
if Self::is_palindrome(&word) {
palindromes.push(word);
}
}
return palindromes;
}
}
Rust details
- Why collect into a vector. Writing
word[0]on a string does not compile: the compiler says the typestrcannot be indexed by an integer. Strings are bytes of UTF-8 text, and a character can take more than one byte ("été"has length 5 but only 3 characters).chars()walks real characters, so the vector's indexes match letters. - Moving the words.
for word in wordshands eachStringover, so it can be moved intopalindromeswithout copying. The cost:wordscan't be used after the loop. - Lending to the helper.
&wordlends the string for the call. The helper takes a&str, and Rust accepts a&Stringthere. Since the word was only lent, the loop can still push it afterwards. - Early return. The first pair that differs settles the answer, so there is no need to look at the rest.
Watching the pairs
For the five-letter word "abcba", n is 5 and the loop runs twice. For the four-letter word "abca", n is 4 and it also runs twice. The pairs compared are:
abcba n=5, loop runs 2 times
i=0 a vs a (index 4)
i=1 b vs b (index 3)
abca n=4, loop runs 2 times
i=0 a vs a (index 3)
i=1 b vs c (index 2)
The middle c of "abcba" is never compared, which is fine: it is its own partner. In "abca" the second pair differs (b against c), so the helper returns false there.
Trying it
["pup", "cat", "noon", "dog"] -> ["pup", "noon"]
["a", "bob", "abba", "ab"] -> ["a", "bob", "abba"]
["kitten", "parrot"] -> []
["bob", "bob"] -> ["bob", "bob"]
The last case shows that repeats are kept: each occurrence is judged on its own.
Moving or borrowing the words
The loop in palindrome_words goes over words itself, not over &words. That choice has a reason: the result is a new vector of String values, and pushing a word into it needs the word itself, not a reference to it. Looping over the vector hands the loop each String by value, so the push can move it without copying.
The price is that the vector is used up. Using words after such a loop is a compile error, borrow of moved value: `words`, and the compiler suggests looping over a slice. That is fine here, because palindrome_words has no use for words once the loop ends. If you looped over &words instead, each word would be a &String and you would have to call clone() before pushing it.
Common mistakes
- Looping to
ninstead ofn / 2. The second half repeats the comparisons of the first half. It gives the right answer but does twice the work. - Using
letters[n - i]. That is off by one; the last index isn - 1, andletters[n]panics for being out of bounds. - Returning
trueinside the loop. One matching pair proves nothing. Only a mismatch lets you decide early. - Dropping duplicates. The task keeps a palindrome every time it appears.
