Where is my logic error in this recursive longest palindrome finder?

Question

My goal is to return the longest palindrome in an array of bytes. My algorithm is:

Branch A
- From the first character to the last, is the string a palindrome? If so return it.
- If not, from the first character to the second last, is the string a palindrome? ...
- If not, from the first character to the third last, is the string a palindrome? ...
- ..
- Are there less than 2 characters left? if so, go to Branch A, but instead of reading from the first character, check from the second one.
- ..
- Are there less than 2 characters left? if so, go to Branch A, but instead of reading from the first character, check from the third one.
- ..
- Are there less than 2 characters left? Return `None.

This problem is iterative by nature but the algorithm doesn't seem to work in either my iterative or recursive solution. So far I've gotten to this:

// slices are upper-bound exclusive
// return expressions are optionally implicit

fn is_palindrome(bytes: &[u8]) -> bool {
    if bytes.len() == 1 {
        true
    } else if bytes.len() == 2 {
        bytes[0] == bytes[1]
    } else if bytes[0] == bytes[bytes.len() - 1] {
        is_palindrome(&bytes[1..bytes.len() - 1])
    } else {
        false
    }
}

fn recurse_palindrome<'a>(s: &'a [u8], start: usize, end: usize) -> Option<&'a [u8]> {
    if start == end {
        if start == s.len() {
            None
        } else {
            // if start < s.len() - 1
            recurse_palindrome(&s, start + 1, s.len() - 1)
        }
    } else if is_palindrome(&s[start..end + 1]) {
        Some(&s[start..end + 1])
    } else {
        recurse_palindrome(&s, start, end - 1)
    }
}

pub fn longest_palindrome<'a>(s: &'a [u8]) -> Option<&'a [u8]> {
    recurse_palindrome(&s, 0, s.len() - 1)
}

// expected answers and tests
#[cfg(test)]
mod test {
    #[test]
    fn is_palindrome() {
        assert_eq!(super::is_palindrome(b"saas"), true); // ok
        assert_eq!(super::is_palindrome(b"ss"), true); // ok
    }

    #[test]
    fn longest_palindrome1() {
        assert_eq!(
            super::longest_palindrome(b"saasdbc").unwrap_or(b""),
            b"saas"
        ); // passes
    }

    #[test]
    fn longest_palindrome() {
        assert_eq!(
            super::longest_palindrome(b"ssaasdbc").unwrap_or(b""),
            b"saas"
        ); // fails; returns b"ss" instead of b"saas"
    }
}

Note that I'm not passing the slice in that case, I'm passing the first and the last index. — noconst, Jan 03 '20 at 14:07
Have you tried debugging? Find a small failing case and debug it. — MrSmith42, Jan 03 '20 at 14:26
I haven't quite understood what `recurse_palindrome` does, but `is_palindrome` is incorrect because `1..bytes.len() - 2` does not include the endpoint, as your comment also says: *`slices are upper-bound exclusive`*. — trent, Jan 03 '20 at 15:48
It looks like your question might be answered by the answers of [How do I compare a vector against a reversed version of itself?](https://stackoverflow.com/q/33348032/155423). If not, please **[edit]** your question to explain the differences. Otherwise, we can mark this question as already answered. — Shepmaster, Jan 03 '20 at 15:50
If the issue I have pointed out is the only problem, this becomes IMO a duplicate of [Expected behavior of `for` loop in rust](https://stackoverflow.com/questions/48979080/expected-behavior-of-for-loop-in-rust/48979113#48979113); but as you seem to already know that, perhaps it was just a typo? — trent, Jan 03 '20 at 15:53
@trentcl I would argue is_palindrome works. The idea is to check the first and the last item of the array, and if they are equal check the second and the second last item in the array, which is `&s[1]` and `&s[s.len() - 2]`. See https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=59d59c5738aa4796ee36edb15998b8cd — noconst, Jan 03 '20 at 19:31
You would be arguing incorrectly. [Print out the argument to `is_palindrome`](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=74fe7c70d4fa5f0937260116879b3758) and you'll quickly see the problem. Notably, [`b"sabs"` is a palindrome according to your logic](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=b5da7593b371c09ef54b776368617c1a). — Shepmaster, Jan 03 '20 at 19:38

score 0 · Answer 1 · answered Jan 03 '20 at 20:48

0

This algorithm doesn't work because it finds the first palindrome from the left instead of the longest one.

answered Jan 03 '20 at 20:48

noconst

639
4
15

Shepmaster · Answer 2 · 2020-01-03T21:30:18.190

I'd use slice::windows to iterate over all of the subslices of a length equal to or less than the original slice. I then find the first subslice that is a palindrome. I also rewrote is_palindrome to be iterative:

fn is_palindrome(mut bytes: &[u8]) -> bool {
    loop {
        match bytes {
            [] | [_] => return true,
            other => {
                let (h, m) = other.split_first().unwrap();
                let (t, m) = m.split_last().unwrap();
                if h != t {
                    return false;
                }
                bytes = m;
            }
        }
    }
}

pub fn longest_palindrome(s: &[u8]) -> Option<&[u8]> {
    (0..s.len())
        .rev()
        .flat_map(|l| s.windows(l + 1))
        .filter(|ss| is_palindrome(ss))
        .next()
}

When advanced slice patterns are stabilized, the is_palindrome function can simplified:

#![feature(slice_patterns)]

fn is_palindrome(mut bytes: &[u8]) -> bool {
    loop {
        match bytes {
            [] | [_] => return true,
            [h, m @ .., t] => {
                if h != t {
                    return false;
                }
                bytes = m;
            }
        }
    }
}

Where is my logic error in this recursive longest palindrome finder?

2 Answers2