20.有效的括号¶

最后更新：2024-05-11-22

链接：https://leetcode.cn/problems/valid-parentheses/description/

题目描述

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

有效字符串需满足：

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

题目示例

示例 1：示例 2：示例 3：

输入： s = "()"

输出： true

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

输出： true

输入： s = "(]"

输出： false

提示：

\(1 <= s.length <= 10^4\)
s 仅由括号 '()[]{}' 组成

解题思路

使用栈的方法，左侧括号时入栈，右侧括号时出栈，如果匹配成功，最终栈是空的

逻辑处理：

遇到左侧括号时，括号入栈
遇到右侧括号，判断右侧括号与栈顶匹配，则出栈，否则返回false

隐藏条件：

括号匹配，则字符个数必然是偶数
入栈出栈，如果遍历过半时，必然是要开始出栈的，否则就是不匹配的
字符全部处理完毕，如果匹配，栈必然已经是空的

C链表实现栈C数组实现栈C栈优化Go切片实现

C
// 定义链表节点结构体
typedef struct Node {
    char data;
    struct Node* next;
} Node;

// 定义栈结构体
typedef struct Stack {
    Node* top;
} Stack;

// 初始化栈
Stack* createStack() {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->top = NULL;
    return stack;
}

// 判断栈是否为空
int isEmpty(Stack* stack) {
    return stack->top == NULL;
}

// 入栈操作
void push(Stack* stack, char value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = stack->top;
    stack->top = newNode;
}

// 出栈操作
char pop(Stack* stack) {
    if (isEmpty(stack)) {
        return -1;
    }
    Node* temp = stack->top;
    char value = temp->data;
    stack->top = temp->next;
    free(temp);
    return value;
}

// 查看栈顶元素
char peek(Stack* stack) {
    if (isEmpty(stack)) {
        return -1;
    }
    return stack->top->data;
}

// 销毁栈，释放所有节点内存
void destroyStack(Stack* stack) {
    Node* temp;
    while (!isEmpty(stack)) {
        temp = stack->top;
        stack->top = stack->top->next;
        free(temp);
    }
    free(stack);
}

char charPairs(char a) {
    if (a == '}') return '{';
    if (a == ']') return '[';
    if (a == ')') return '(';
    return 0;
}

bool isValid(char* s) {
    unsigned int n = 0;
    unsigned int i = 0;
    unsigned int top = 0;
    Stack *stack = NULL;

    n = strlen(s);
    // 必须是偶数，如果是奇数，肯定是不满足条件的
    if ((n % 2) != 0) {
        return false;
    }

    stack = createStack();
    // 遍历字符串，记录top，当左侧括号出现时，入栈，top++
    for (i = 0; i < n; i++) {
        // 超过一半的时候，就需要开始出栈了，否则必然不匹配
        if (top > n/2) {
            destroyStack(stack);
            return false;
        }
        char ch = charPairs(s[i]);
        // 找到一个左侧括号，直接入栈
        if (ch == 0) { // 找到左侧括号
            push(stack, s[i]);
        } else {
            if (isEmpty(stack) || (peek(stack) != ch)) {
                destroyStack(stack);
                return false;
            }
            pop(stack);
        }
    }

    // 如果括号是匹配的，栈一定是空的
    if (isEmpty(stack)) {
        return true;
    }
    destroyStack(stack);
    return false;
}

C
bool CheckBracketMatchForArr(char sL, char *stack,  unsigned int *top)
{
    unsigned int index = *top;
    // 没有入栈，或者与栈顶不是一对，返回false
    if ((index == 0) || (stack[index - 1] != sL)) {
        return false;
    }

    // 出栈
    stack[index] = '\0';
    index--;
    *top = index;
    return true;
}

bool isValidByArray(char* s) {
    unsigned int n = 0;
    unsigned int i = 0;
    unsigned int top = 0;
    char *stack = NULL;

    n = strlen(s);
    // 必须是偶数，如果是奇数，肯定是不满足条件的
    if ((n % 2) != 0) {
        return false;
    }

    // 使用数组，表示栈数据存储，申请内存
    stack = (char*)malloc(n);
    if (stack == NULL) {
        return false;
    }
    memset(stack,0,n);

    // 遍历字符串，记录top，当左侧括号出现时，入栈，top++
    for (i = 0; i < n; i++) {
        // 超过一半的时候，就需要开始出栈了，否则必然不匹配
        if (top > n/2) {
            free(stack);
            return false;
        }

        // 找到一个左侧括号，直接入栈
        if ((s[i] == '(')  || (s[i] == '{') || (s[i] == '[')) { // 找到左侧括号
            stack[top] = s[i];
            top++;
            continue;
        }

        // 如果是右侧括号，当与栈顶是一对的时候，进行出栈，否则直接返回false
        if ((s[i] == ')') && (CheckBracketMatchForArr('(', stack, &top) == false))
        {
            return false;
        }

        if ((s[i] == '}') && (CheckBracketMatchForArr('{', stack, &top) == false)) 
        {
            return false;
        }

        if ((s[i] == ']') && (CheckBracketMatchForArr('[', stack, &top) == false)) 
        {
            return false;
        }
    }

    // 如果括号是匹配的，则top是一定为0
    return top == 0;
}

bool isValid(char* s) {
    return isValidByArray(s);
}

C
bool CheckBracketMatchForArr(char sL, char *stack,  unsigned int *top)
{
    unsigned int index = *top;
    // 没有入栈，或者与栈顶不是一对，返回false
    if ((index == 0) || (stack[index - 1] != sL)) {
        return false;
    }

    // 出栈
    stack[index] = '\0';
    index--;
    *top = index;
    return true;
}

char pairs(char a) {
    if (a == '}') return '{';
    if (a == ']') return '[';
    if (a == ')') return '(';
    return 0;
}

bool isValidByArrayWithParis(char* s) {
    unsigned int n = 0;
    unsigned int i = 0;
    unsigned int top = 0;
    char *stack = NULL;

    n = strlen(s);
    // 必须是偶数，如果是奇数，肯定是不满足条件的
    if ((n % 2) != 0) {
        return false;
    }

    // 使用数组，表示栈数据存储，申请内存
    stack = (char*)malloc(n);
    if (stack == NULL) {
        return false;
    }
    memset(stack,0,n);

    // 遍历字符串，记录top，当左侧括号出现时，入栈，top++
    for (i = 0; i < n; i++) {
        // 超过一半的时候，就需要开始出栈了，否则必然不匹配
        if (top > n/2) {
            free(stack);
            return false;
        }
        char ch = pairs(s[i]);
        // 找到一个左侧括号，直接入栈
        if (ch != 0) { // 找到左侧括号
            stack[top] = s[i];
            top++;
        } else {
            if (CheckBracketMatchForArr(ch, stack, &top) == false) {
                free(stack);
                return false;
            }
        }
    }

    // 如果括号是匹配的，则top是一定为0
    free(stack);
    return top == 0;
}

bool isValid(char* s) {
    return isValidByArrayWithParis(s);
}

Go
func isValid(s string) bool {
    strlen := len(s)
    if strlen % 2 == 1 {
        return false
    }
    pairs := map[byte]byte{
        ')': '(',
        ']': '[',
        '}': '{',
    }
    var stack []byte
    for i := 0; i < strlen; i++ {
        // 如果在过一半的时候，top还没有开始出栈，则肯定不匹配
        if (len(stack) > strlen/2) {
            return false;
        }

        // 题目指定只有 '('，')'，'{'，'}'，'['，']'几个字符串，有匹配到右侧括号
        if pairs[s[i]] > 0 {
            // 右侧括号，如果字符串有效，则左侧括号必然已经在栈中，并且是在栈顶
            if len(stack) == 0 || stack[len(stack)-1] != pairs[s[i]] {
                return false
            }
            // 满足条件，出栈
            stack = stack[:len(stack)-1]
        } else {
            // 不是右侧括号，入栈
            stack = append(stack, s[i])
        }
    }

    // 如果括号是匹配的，最终结果，栈一定是空的
    return len(stack) == 0
}