2021/04/16
回溯法
impl Solution {
pub fn partition(s: String) -> Vec<Vec<String>> {
let mut res = vec![];
Solution::partition_0(&s, 0, 0, &mut vec![], &mut res);
return res;
}
pub fn partition_0(s: &String, i: usize, j: usize, cur: &mut Vec<String>, res: &mut Vec<Vec<String>>) {
if j == s.len() {
if i == j {
res.push(cur.clone());
}
return;
}
if Solution::is_palindrome(&s[i..=j]) {
cur.push(String::from(&s[i..=j]));
Solution::partition_0(s, j + 1, j + 1, cur, res);
cur.pop();
}
Solution::partition_0(s, i, j + 1, cur, res);
}
fn is_palindrome(s: &str) -> bool {
let mut i = 0 as i32;
let mut j = (s.len() - 1) as i32;
while i <= j {
if s.chars().nth(i as usize).unwrap() != s.chars().nth(j as usize).unwrap() {
return false;
}
i += 1;
j -= 1;
}
return true;
}
}
递归的时候不产生 clone
耍了一波生命周期标注，让递归的时候不产生 clone, 最后把 Vec<Vec<&str>> 转成 Vec<Vec<String>> 的时候，会把原本在递归的时候的 clone 的开销补回来。但没想到提交代码总耗时还增加了（116ms -> 140~160ms），本地压测时也发现耗时增加了。
impl Solution {
pub fn partition(s: String) -> Vec<Vec<String>> {
let mut res = vec![];
Solution::partition_0(&s, 0, 0, &mut vec![], &mut res);
let x: Vec<_> = res.into_iter().map(|i| i.into_iter().map(|j| String::from(j)).collect::<Vec<String>>()).collect();
return x;
}
pub fn partition_0<'a>(s: &'a String, i: usize, j: usize, cur: &mut Vec<&'a str>, res: &mut Vec<Vec<&'a str>>) {
if j == s.len() {
if i == j {
res.push(cur.clone()); // 这里 clone 的是 Vec<&str>，免不了的
}
return;
}
if Solution::is_palindrome(&s[i..=j]) {
cur.push(&s[i..=j]); // 这里去掉了 clone，性能确实提高了
Solution::partition_0(s, j + 1, j + 1, cur, res);
cur.pop();
}
Solution::partition_0(s, i, j + 1, cur, res);
}
fn is_palindrome(s: &str) -> bool {
let mut i = 0 as i32;
let mut j = (s.len() - 1) as i32;
while i <= j {
if s.chars().nth(i as usize).unwrap() != s.chars().nth(j as usize).unwrap() {
return false;
}
i += 1;
j -= 1;
}
return true;
}
}
尝试了把转换的操作用明显性能更高的方式写，发现仍然会更慢。
pub fn partition(s: String) -> Vec<Vec<String>> {
let mut res = vec![];
Solution::partition_0(&s, 0, 0, &mut vec![], &mut res);
let mut collector = Vec::with_capacity(res.len());
for r in res.iter() {
let mut v = Vec::with_capacity(r.len());
for i in r {
v.push(i.to_string());
}
collector.push(v);
}
// let x: Vec<_> = res.into_iter().map(|i| i.into_iter().map(|j| String::from(j)).collect::<Vec<String>>()).collect();
return collector;
}