每日小刷
| Runtime | Memory |
|---|---|
| 16ms | 2.5m |
// 三種方法
use std::cmp;
impl Solution {
// 逆轉(zhuǎn)數(shù)組之后尋找最大相同字符串 暴力法
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()
}
// 動態(tài)規(guī)劃
// 尋找狀態(tài)轉(zhuǎn)移方程
// 如果p(i,j)是會還數(shù)列那么p(i+1,j-1)必然也是
// p(i+1,j-1)是回環(huán)數(shù)列 并且Si==Sj 推出p(i,j)是回環(huán)數(shù)列
// 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 要求太變態(tài)了
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和基礎算法
