20.有效的括号

发表于 | 分类于
字数统计: 429 | 阅读时长 ≈ 1

题目描述

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

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

1
2
输入: "()"
输出: true

示例 2:

1
2
输入: "()[]{}"
输出: true

示例 3:

1
2
输入: "(]"
输出: false

示例 4:

1
2
输入: "([)]"
输出: false

示例 5:

1
2
输入: "{[]}"
输出: true

题解

思路

使用数组模拟栈操作，遇到 ( { [ 时入栈，遇到 ) } ] 时出栈（当且仅当待入栈符号与栈顶元素相差1或2时，才能出栈，否则仍入栈），遍历整个字符串后，栈空则匹配成功；否则失败。

C代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool isValid(char* s)
{
    int top = 0;
    char* str = malloc(strlen(s) + 1);
    //一次性申请s字符串所占空间，+1是因为'\0'
    int i = 0;
    while (s[i] != '\0') {
        if (s[i] == '(' || s[i] == '{' || s[i] == '[')
            str[++top] = s[i];
        else if (s[i] == str[top] + 1 || s[i] == str[top] + 2)
            //'('与')'的ASCII值差1，'['与']'，'{'与'}'的ASCII值差2
            top--;
        else
            return 0;
        i++;
    }
    return !top;
}

思路

当字符串中存在已匹配的字符串时，就用空字符串替代；如果字符串最后为空，则全部匹配；否则失败。

Python代码

1
2
3
4
5
6
7
class Solution:
    def isValid(self, s: str) -> bool:
        while '()' in s or '[]' in s or '{}'in s:
            s = s.replace('()', '')
            s = s.replace('[]', '')
            s = s.replace('{}', '')
        return s == ''