每日小刷
leetcode
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
}
}
