rust leetcode 最大回文序列
- 2019 年 11 月 20 日
- 筆記
每日小刷
|
Runtime |
Memory |
|---|---|
|
16ms |
2.5m |
// 三种方法 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 } }
