rust leetcode 最大回文序列

每日小刷

leetcode

// 三种方法
use std::cmp;
impl Solution {
    // 逆转数组之后寻找最大相同字符串 暴力法
    pub fn longest_palindrome_volence(s: String) -> String {
        let chars: Vec<char> = s.chars().collect();
        let mut chars_reverse: Vec<char> = s.chars().collect();
        chars_reverse.reverse();
        let mut start = 0;
        let mut end = 0;
        let mut max = 0;
        for i in 0..chars.len() {
            for j in 0..chars_reverse.len() {
                if chars[i] == chars_reverse[j] {
                    let mut inner_i = i;
                    let mut inner_j = j;
                    while chars[inner_i] == chars_reverse[inner_j] {
                        if (inner_i + 1 - i) > max {
                            max = inner_i - i + 1;
                            start = i;
                            end = inner_i;
                        }
                        inner_i += 1;
                        inner_j += 1;
                        if inner_i == chars.len() || inner_j == chars.len() {
                            break;
                        }
                    }
                }
            }
        }
        s[start..end + 1].to_owned()
    }

    // 动态规划
    // 寻找状态转移方程
    // 如果p(i,j)是会还数列那么p(i+1,j-1)必然也是
    // p(i+1,j-1)是回环数列 并且Si==Sj 推出p(i,j)是回环数列
    // acaca 0 1 0 2
    pub fn longest_palindrome_dynamic(s: String) -> String {
        let mut longest = vec![vec![false; s.len()]; s.len()];
        let chars: Vec<char> = s.chars().collect();
        let mut max = 0;
        let mut start = 0;
        let mut end = 0;
        // i 代表起始坐标 j代表终止坐标
        for j in 0..s.len() {
            for i in 0..j + 1 {
                if j - i < 2 {
                    longest[i][j] = chars[i] == chars[j];
                } else {
                    longest[i][j] = longest[i + 1][j - 1] && chars[i] == chars[j];
                }
                if j - i > max && longest[i][j] {
                    start = i;
                    end = j;
                    max = j - i;
                }
            }
        }
        s[start..end + 1].to_owned()
    }

    // 寻找中心
    pub fn longest_palindrome(s: String) -> String {
        if s.len() < 1 {
            return String::from("");
        }
        if s.len() == 1 {
            return s;
        }
        let chars: Vec<char> = s.chars().collect();
        let mut max = 0;
        let mut start = 0;
        let mut end = 0;
        for i in 0..chars.len() {
            let l1 = Solution::aroundCenter(&chars, i, i);
            let l2 = Solution::aroundCenter(&chars, i, i + 1);
            let len = cmp::max(l1, l2);
            println!("len:{}", len);
            if len > max {
                max = len;
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        s[start..end + 1].to_owned()
    }

    // rust usize i32 要求太变态了
    pub fn aroundCenter(chars: &Vec<char>, left_center: usize, right_center: usize) -> usize {
        let mut L = left_center;
        let mut R = right_center;
        while L >= 0 && R < chars.len() && chars[L] == chars[R] {
            if L == 0 {
                return R - L + 1;
            }
            L -= 1;
            R += 1;
        }
        R - L - 1
    }
}

好好学习rust和基础算法