How do I compare a vector against a reversed versi

Question

Why won't this compile?

fn isPalindrome<T>(v: Vec<T>) -> bool {
  return v.reverse() == v;
}

I get

error[E0308]: mismatched types
 --> src/main.rs:2:25
  |
2 |   return v.reverse() == v;
  |                         ^ expected (), found struct `std::vec::Vec`
  |
  = note: expected type `()`
             found type `std::vec::Vec<T>`

Answer 1

Since you only need to look at the front half and back half, you can use the DoubleEndedIterator trait (methods .next() and .next_back()) to look at pairs of front and back elements this way:

/// Determine if an iterable equals itself reversed
fn is_palindrome<I>(iterable: I) -> bool
where
    I: IntoIterator,
    I::Item: PartialEq,
    I::IntoIter: DoubleEndedIterator,
{
    let mut iter = iterable.into_iter();
    while let (Some(front), Some(back)) = (iter.next(), iter.next_back()) {
        if front != back {
            return false;
        }
    }

    true
}

(run in playground)

This version is a bit more general, since it supports any iterable that is double ended, for example slice and chars iterators.

It only examines each element once, and it automatically skips the remaining middle element if the iterator was of odd length.

Answer 2

Read up on the documentation for the function you are using:

Reverse the order of elements in a slice, in place.

Or check the function signature:

fn reverse(&mut self)

The return value of the method is the unit type, an empty tuple (). You can't compare that against a vector.

---

Stylistically, Rust uses 4 space indents, snake_case identifiers for functions and variables, and has an implicit return at the end of blocks. You should adjust to these conventions in a new language.

Additionally, you should take a &[T] instead of a Vec<T> if you are not adding items to the vector.

To solve your problem, we will use iterators to compare the slice. You can get forward and backward iterators of a slide, which requires a very small amount of space compared to reversing the entire array. Iterator::eq allows you to do the comparison succinctly.

You also need to state that the T is comparable against itself, which requires Eq or PartialEq.

fn is_palindrome<T>(v: &[T]) -> bool
where
    T: Eq,
{
    v.iter().eq(v.iter().rev())
}

fn main() {
    println!("{}", is_palindrome(&[1, 2, 3]));
    println!("{}", is_palindrome(&[1, 2, 1]));
}

If you wanted to do the less-space efficient version, you have to allocate a new vector yourself:

fn is_palindrome<T>(v: &[T]) -> bool
where
    T: Eq + Clone,
{
    let mut reverse = v.to_vec();
    reverse.reverse();
    reverse == v
}

fn main() {
    println!("{}", is_palindrome(&[1, 2, 3]));
    println!("{}", is_palindrome(&[1, 2, 1]));
}

Note that we are now also required to Clone the items in the vector, so we add that trait bound to the method.