algorithm - 在这个递归最长回文查找器中，我的逻辑错误在哪里？

Question

我的目标是返回字节数组中最长的回文。我的算法是：

• 分行 A

  • 从第一个字符到最后一个字符，字符串是回文吗？如果是这样，请将其退回。
  • 如果不是，从第一个字符到倒数第二个，字符串是回文吗？...
  • 如果不是，从第一个字符到倒数第三个字符，字符串是回文吗？...
  • ..
  • 剩下的字符少于 2 个吗？如果是这样，转到分支 A，但不是从第一个字符读取，而是从第二个字符开始检查。
  • ..
  • 剩下的字符少于 2 个吗？如果是这样，转到分支 A，但不是从第一个字符读取，而是从第三个字符开始检查。
  • ..
  • 剩下的字符少于 2 个吗？返回`无。

这个问题本质上是迭代的，但该算法似乎不适用于我的迭代或递归解决方案。到目前为止，我已经做到了：

// 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"
    }
}

标签： algorithmrecursionrustpalindrome

Answer 1

这个算法不起作用，因为它从左边找到第一个回文而不是最长的回文。