删除无效的括号

Category	Difficulty	Likes	Dislikes
algorithms	Hard (55.14%)	796	-

Tags

depth-first-search | breadth-first-search

Companies

facebook

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回。

示例 1：

1
2
输入：s = "()())()"
输出：["(())()","()()()"]

示例 2：

1
2
输入：s = "(a)())()"
输出：["(a())()","(a)()()"]

示例 3：

1
2
输入：s = ")("
输出：[""]

提示：

1 <= s.length <= 25
s 由小写英文字母以及括号 '(' 和 ')' 组成
s 中至多含 20 个括号

Discussion | Solution

解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
impl Solution {
    /// ## 解题思路
    /// - 广度优先搜索
    pub fn remove_invalid_parentheses(s: String) -> Vec<String> {
        let mut set = std::collections::HashSet::new();
        set.insert(s);  // 
        while !set.is_empty() {
            let mut res = Vec::new();

            // 判断set中各个字符串是否有效
            for s in set.iter() {   
                if Solution::is_valid(s) {  //将有效的字符串加入到结果集中
                    res.push(s.clone());
                }
            }

            // 如果结果集不为空，则输出结果
            if !res.is_empty() {
                return res;
            }

            // 依次删除当前集中的字符
            let mut next_set = std::collections::HashSet::new();
            for s in set.iter() { 
                for i in 0..s.len() {
                    let mut s = s.clone();
                    s.remove(i);
                    next_set.insert(s);
                }
            }

            set = next_set;
        }

        vec![]
    }

    fn is_valid(s: &str) -> bool {
        let mut count = 0;
        for c in s.chars() {
            match c {
                '(' => count += 1,
                ')' => {
                    count -= 1;
                    if count < 0 {
                        return false;
                    }
                }
                _ => {}
            }
        }

        return count == 0;
    }
}

删除无效的括号

删除无效的括号

解法

相关文章：