灯的个人博客

forever young,forever weeping.

0%

2023-02-17-xnbcaj

发表于 更新于 分类于

有效的括号

题目

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = “()”
输出：true
示例 2：

输入：s = “()[]{}”
输出：true
示例 3：

输入：s = “(]”
输出：false

提示：

1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成

题解

个人题解

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
impl Solution {
    pub fn is_valid(s: String) -> bool {
        let mut stack: Vec<char> = Vec::new();
        for c in s.chars() {
            if c == '{' {
                stack.push('}')
            } else if c == '[' {
                stack.push(']')
            } else if c == '(' {
                stack.push(')')
            } else {
                if let Some(i) = stack.pop() {
                    if i == c {
                        continue;
                    } else {
                        return false;
                    }
                } else {
                    return false;
                }
            }
        }
        stack.is_empty()
    }
}

官方题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#[allow(dead_code)]
impl Solution {
    pub fn is_valid(s: String) -> bool {
        let mut res: Vec<char> = Vec::with_capacity(s.len());
        let mut pre: Option<&char>;
        for c in s.chars() {
            pre = res.last();
            match (pre, c) {
                (Some('{'), '}') | (Some('['), ']') | (Some('('), ')') => {
                    res.pop();
                }
                _ => res.push(c),
            }
        }
        res.is_empty()
    }
}

思路

原本也没啥思路，就想着怎么处理字符串

然后发现解答里面有关于栈的问题，看了别人的解体思路后，比较明朗

匹配到左括号，向栈推入右括号

如果匹配到右括号，就把栈顶的括号推出，判断是不是为当前的右括号，如果是，代表括号闭合，如果不是，直接失败

匹配到右括号空栈也直接失败

最后判断栈的长度是不是为 0，如果为 0，代表完全匹配

emm

示例的代码写的比较精简，感觉可以复现一次

链接