跳转至

20. 有效的括号

难度：简单

题目

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

有效字符串需满足：

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

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

示例 4：

输入：s = "([)]"
输出：false

示例 5：

输入：s = "{[]}"
输出：true

Reference

题解

使用栈模拟匹配过程

  • 遇到左括号时入栈；
  • 遇到右括号时，检查栈顶括号是否与右括号匹配，若匹配则出栈，否则返回false；
  • 完成匹配过程后检查栈是否为空，若为空返回true，否则返回false。
bool isValid(char * s){
    int maxLen = strlen(s), top = 0;
    char *holding = malloc(sizeof(char) * maxLen), *cur = s;
    while(*cur)
    {
        switch(*cur)
        {
            case '(':
            case '[':
            case '{':
                holding[top] = *cur;
                top++;
                break;
            case ')':
                if (top == 0 || holding[top - 1] != '(')
                    return false;
                top--;
                break;
            case ']':
            case '}':
                if (top == 0 || holding[top - 1] != (*cur) - 2)
                    return false;
                top--;
                break;
        }
        cur++;
    }
    return !top;
}

评论