20. 有效的括号

- 2 mins read

20. 有效的括号

LeetCode 20. 有效的括号

题目描述

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

有效字符串需满足：

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

示例

  • 示例 1

    输入: s = “()”

    输出: true

  • 示例 2

    输入: “()[]{}”

    输出: true

  • 示例 3

    输入: s = “(]”

    输出: false

  • 示例 4

    输入: s = “([)]”

    输出: false

  • 示例 5

    输入: s = “{[]}”

    输出: true

解题模版

bool isValid(char * s){
}

解题思路

  1. 使用一个栈结构StackNode,遍历字符s遇到(, [, {将对应的闭合字符push到栈中。
  2. 遇到非(, [, {的字符执行pop操作，判断栈顶字符是否与当前字符匹配，匹配pop,否则返回false.
  3. 最后堆栈如果为空返回true

解答

struct StackNode {
    char v;
    struct StackNode* next;
};

struct StackNode* ifPop(struct StackNode* head, char c) {
    if(!head) {
        return NULL;
    }
    if(head->v == c) {
        struct StackNode* next = head->next;
        free(head);
        return next;
    }
    return head;
}

struct StackNode* push(struct StackNode* head, char c) {
    struct StackNode* node = (struct StackNode*) malloc(sizeof(struct StackNode));
    node->next = NULL;
    node->v = c;
    if(head) {
        node->next = head;
    }
    return node;
}

bool isValid(char * s){
    struct StackNode* stack = NULL;
    char *p = s;
    char c = *p;

    while(c != '\0') {
        //printf("%c", c);
        switch(c) {
            case '(' :
            stack = push(stack, ')');
            break;
            case '{' :
            stack = push(stack, '}');
            break;
            case '[' :
            stack = push(stack, ']');
            break;
            default:
            if(stack == NULL) {
                return false;
            }
            struct StackNode* t = stack;
            stack = ifPop(stack, c);
            if(stack == t) {
                return false;
            }
        }
        p++;
        c = *p;
    }
    return stack == NULL;
}