leetcode_rust/
longest_palindrome.rs

1#![allow(dead_code)]
2
3// dp
4pub fn longest_palindrome(s: String) -> String {
5    use std::iter;
6    let s = s.into_bytes();
7    if s.len() <= 1 {
8        return String::from_utf8(s).unwrap();
9    }
10    let mut dp: Vec<Vec<bool>> = Vec::with_capacity(s.len());
11    for _ in 0..s.len() {
12        dp.push(iter::repeat(true).take(s.len()).collect())
13    }
14    let mut final_i = 0;
15    let mut final_j = 0;
16    let mut longest = 0;
17    dp[s.len() - 1][s.len() - 1] = true;
18    for i in 0..s.len() - 1 {
19        dp[i][i] = true;
20        let j = i + 1;
21        dp[i][j] = s[i] == s[j];
22        if dp[i][j] && longest < j - i + 1 {
23            longest = j - i + 1;
24            final_i = i;
25            final_j = j;
26        }
27    }
28    for i in (0..s.len()).rev() {
29        for j in i + 1..s.len() {
30            dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j];
31            if dp[i][j] && longest <= j - i + 1 {
32                longest = j - i + 1;
33                final_i = i;
34                final_j = j;
35            }
36        }
37    }
38
39    let temp = String::from_utf8(s).unwrap();
40    String::from(&temp[final_i..=final_j])
41}
42
43#[cfg(test)]
44mod tests {
45    use super::*;
46
47    #[test]
48    fn test1() {
49        assert_eq!(
50            longest_palindrome(String::from("babad")),
51            String::from("bab")
52        );
53        assert_eq!(longest_palindrome(String::from("")), String::from(""));
54        assert_eq!(longest_palindrome(String::from("cbbd")), String::from("bb"));
55        assert_eq!(longest_palindrome(String::from("abcda")), String::from("a"));
56        assert_eq!(longest_palindrome(String::from("ccc")), String::from("ccc"));
57    }
58}
leetcode_rust/longest_palindrome.rs

leetcode_rust/
longest_palindrome.rs
