2021/04/14
在叶子节点收集 (148ms)
use std::collections::{HashSet};
impl Solution {
pub fn remove_invalid_parentheses(s: String) -> Vec<String> {
if Solution::valid(&s) == 0 {
return vec![s];
}
let mut res = HashSet::new();
Solution::remove_invalid_parentheses_0(&s, 0, &mut "".to_string(), &mut res);
let max_len = res.iter().map(|s| s.len()).max().unwrap();
let x: Vec<_> = res.into_iter().filter(|s| s.len() == max_len).collect();
return x;
}
fn valid(cur: &String) -> i32 {
let mut sum = 0;
for c in cur.chars() {
sum += match c {
'(' => 1,
')' => -1,
_ => 0
};
if sum < 0 {
return -1;
}
}
return sum;
}
fn remove_invalid_parentheses_0(s: &String, curi: usize, cur: &mut String, collector: &mut HashSet<String>) {
if curi == s.len() {
if Solution::valid(cur) == 0 {
collector.insert(cur.clone());
}
return;
}
let ch = s.chars().nth(curi).unwrap();
// 选择这个 ch
cur.push(ch);
if Solution::valid(cur) >= 0 {
Solution::remove_invalid_parentheses_0(s, curi + 1, cur, collector);
}
cur.pop();
// 如果不是字母的话，可以不选
if ch == '(' || ch == ')' {
Solution::remove_invalid_parentheses_0(s, curi + 1, cur, collector);
}
}
}
增加了一个剪枝(48ms)
增加一个剪枝。由于我们的 valid 函数会返回当前被右括号抵消后还剩下的左括号 ‘(‘ 的个数，如果当前已经搜到了 s 的第 i 个元素，并且剩下的 s.len() - i 个元素中没有足够的右括号 ‘)’ 来抵消这些左括号，那么也不用搜了。
use std::collections::{HashSet};
impl Solution {
pub fn remove_invalid_parentheses(s: String) -> Vec<String> {
if Solution::valid(&s) == 0 {
return vec![s];
}
let mut res = HashSet::new();
Solution::remove_invalid_parentheses_0(&s, 0, &mut "".to_string(), &mut res);
let max_len = res.iter().map(|s| s.len()).max().unwrap();
let x: Vec<_> = res.into_iter().filter(|s| s.len() == max_len).collect();
return x;
}
fn valid(cur: &String) -> i32 {
let mut sum = 0;
for c in cur.chars() {
sum += match c {
'(' => 1,
')' => -1,
_ => 0
};
if sum < 0 {
return -1;
}
}
return sum;
}
fn neg_sum(s: &str) -> i32 {
let mut sum = 0;
for c in s.chars() {
sum += match c {
')' => -1,
_ => 0,
};
}
return sum;
}
fn remove_invalid_parentheses_0(s: &String, curi: usize, cur: &mut String, collector: &mut HashSet<String>) {
if curi == s.len() {
if Solution::valid(cur) == 0 {
collector.insert(cur.clone());
}
return;
}
let ch = s.chars().nth(curi).unwrap();
// 选择这个 ch
cur.push(ch);
let cur_v = Solution::valid(cur);
// 如果后面所有的右括号都不足以抵消当前剩下的左括号数了，就别搜了
if cur_v >= 0 && Solution::neg_sum(&s[curi+1..]) + cur_v <= 0 {
Solution::remove_invalid_parentheses_0(s, curi + 1, cur, collector);
}
cur.pop();
// 如果不是字母的话，可以不选
if ch == '(' || ch == ')' {
Solution::remove_invalid_parentheses_0(s, curi + 1, cur, collector);
}
}
}
继续剪枝(8ms)
维护一个全局变量 MAX_LEN 记录当前最长的合法字符串的长度，如果发现了大于这个长度的结果，则清空已有的结果，这样结果集中的结果一定是最长的，不需要递归结束后再去筛出最长的。
增加一个剪枝：假设现在搜到了 s 的第 i 个位置，如果 cur 把剩下所有的 s.len() - i 个字符全部添加进来都达不到 MAX_LEN 了，那么也不用搜了。
use std::collections::{HashSet};
static mut MAX_LEN: i32 = -1;
impl Solution {
pub fn remove_invalid_parentheses(s: String) -> Vec<String> {
if Solution::valid(&s) == 0 {
return vec![s];
}
let mut res = HashSet::new();
unsafe {
MAX_LEN = 0;
Solution::remove_invalid_parentheses_0(&s, 0, &mut "".to_string(), &mut res)
}
let x: Vec<_> = res.into_iter().collect();
return x;
}
fn valid(cur: &String) -> i32 {
let mut sum = 0;
for c in cur.chars() {
sum += match c {
'(' => 1,
')' => -1,
_ => 0
};
if sum < 0 {
return -1;
}
}
return sum;
}
fn neg_sum(s: &str) -> i32 {
let mut sum = 0;
for c in s.chars() {
sum += match c {
')' => -1,
_ => 0,
};
}
return sum;
}
unsafe fn remove_invalid_parentheses_0(s: &String, curi: usize, cur: &mut String, collector: &mut HashSet<String>) {
if curi == s.len() {
let len = cur.len() as i32;
if Solution::valid(cur) == 0 && len >= MAX_LEN {
if len > MAX_LEN {
MAX_LEN = len;
collector.clear();
}
collector.insert(cur.clone());
}
return;
}
let ch = s.chars().nth(curi).unwrap();
// 选择这个 ch
cur.push(ch);
let cur_v = Solution::valid(cur);
if cur_v >= 0 // 如果当前的字符还是合法的
&& (cur.len() + (s.len() - curi)) as i32 >= MAX_LEN // 如果剩下的字符加起来有可能超过当前最长合法字符串
&& Solution::neg_sum(&s[curi + 1..]) + cur_v <= 0 // 如果剩下的')'有可能低消被剩下的 '('
{
Solution::remove_invalid_parentheses_0(s, curi + 1, cur, collector);
}
cur.pop();
// 如果不是字母的话，可以不选
if ch == '(' || ch == ')' {
Solution::remove_invalid_parentheses_0(s, curi + 1, cur, collector);
}
}
}
继续优化，还是8ms
neg_sum 可以预计算，不需要每次都去算，get_neg_arr 这个函数本身就是一个小算法题了。
use std::collections::{HashSet};
static mut MAX_LEN: i32 = -1;
impl Solution {
fn get_neg_arr(s: &String) -> Vec<i32> {
let mut neg_sum_arr = vec![];
let mut neg = 0;
for ch in s.chars().rev() {
neg += match ch {
')' => -1,
_ => 0,
};
neg_sum_arr.push(neg);
}
neg_sum_arr.reverse();
neg_sum_arr.rotate_left(1);
*neg_sum_arr.last_mut().unwrap() = 0;
return neg_sum_arr;
}
pub fn remove_invalid_parentheses(s: String) -> Vec<String> {
if Solution::valid(&s) == 0 {
return vec![s];
}
let mut res = HashSet::new();
let neg_sum_arr = Solution::get_neg_arr(&s);
unsafe {
MAX_LEN = 0;
Solution::remove_invalid_parentheses_0(&s, 0, &mut "".to_string(), &neg_sum_arr, &mut res)
}
let x: Vec<_> = res.into_iter().collect();
return x;
}
fn valid(cur: &String) -> i32 {
let mut sum = 0;
for c in cur.chars() {
sum += match c {
'(' => 1,
')' => -1,
_ => 0
};
if sum < 0 {
return -1;
}
}
return sum;
}
unsafe fn remove_invalid_parentheses_0(s: &String, curi: usize, cur: &mut String, neg_sum_arr: &Vec<i32>, collector: &mut HashSet<String>) {
if curi == s.len() {
let len = cur.len() as i32;
if Solution::valid(cur) == 0 && len >= MAX_LEN {
if len > MAX_LEN {
MAX_LEN = len;
collector.clear();
}
collector.insert(cur.clone());
}
return;
}
let ch = s.chars().nth(curi).unwrap();
cur.push(ch);
let cur_v = Solution::valid(cur);
if cur_v >= 0
&& (cur.len() + (s.len() - curi)) as i32 >= MAX_LEN
&& neg_sum_arr[curi] + cur_v <= 0
{
Solution::remove_invalid_parentheses_0(s, curi + 1, cur, neg_sum_arr, collector);
}
cur.pop();
if ch == '(' || ch == ')' {
Solution::remove_invalid_parentheses_0(s, curi + 1, cur, neg_sum_arr, collector);
}
}
}
在非叶子节点就收集(180ms)
这个是自己意识流+调试写出来的，作为反面教材。
use std::collections::{HashSet};
impl Solution {
pub fn remove_invalid_parentheses(s: String) -> Vec<String> {
if Solution::valid(&s) == 0 {
return vec![s];
}
let mut vis = (0..s.len()).map(|x| false).collect();
let mut res = HashSet::new();
Solution::remove_invalid_parentheses_0(&s, 0, &mut "".to_string(), &mut vis, &mut res);
let maxLen = res.iter().map(|s| s.len()).max().unwrap();
let x: Vec<_> = res.into_iter().filter(|s| s.len() == maxLen).collect();
return x;
}
fn valid(cur: &String) -> i32 {
let mut sum = 0;
for c in cur.chars() {
sum += match c {
'(' => 1,
')' => -1,
_ => 0
};
if sum < 0 {
return -1;
}
}
return sum;
}
fn remove_invalid_parentheses_0(s: &String, curi: usize, cur: &mut String, vis: &mut Vec<bool>, collector: &mut HashSet<String>) {
if Solution::valid(cur) == 0 {
collector.insert(cur.clone());
}
if curi >= s.len() || vis[curi] {
return;
}
let ch = s.chars().nth(curi).unwrap();
// 如果不是字母的话，可以不选
if ch == '(' || ch == ')' {
Solution::remove_invalid_parentheses_0(s, curi + 1, cur, vis, collector);
}
// 选择这个 ch
cur.push(ch);
vis[curi] = true;
if Solution::valid(cur) >= 0 {
Solution::remove_invalid_parentheses_0(s, curi + 1, cur, vis, collector);
}
cur.pop();
vis[curi] = false;
}
}