LeetCode第二十题：有效的括号

题目来源：LeetCode第二十题

1.题目描述

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

有效字符串需满足：

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

示例 1：

输入：s = "()"

输出：true

提示：

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

2.解题思路

解法一：栈

• 描述：创建一个空栈来保存遍历字符串时遇到的左括号。逐字符检查给定的字符串。所有字符检查完毕后，检查栈是否为空。
• 时间复杂度：O(n)。n 是字符串的长度。我们需要遍历字符串一次。
• 空间复杂度：O(n)。
• 参考代码：

java版：

class Solution {
    public boolean isValid(String s) {
        // 创建一个栈来存放左括号
        Stack<Character> stack = new Stack<>();
        // 遍历字符串的每个字符
        for (char c : s.toCharArray()) {
            // 如果是左括号，将其推入栈中
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                // 如果栈为空，说明没有对应的左括号可以匹配当前右括号
                if (stack.isEmpty()) {
                    return false;
                }
                // 弹出栈顶元素，检查是否与当前右括号匹配
                char top = stack.pop();
                if ((c == ')' && top != '(') || (c == '}' && top != '{') || (c == ']' && top != '[')) {
                    return false;
                }
            }
        }
        // 如果栈为空，说明所有左括号都匹配了对应的右括号
        return stack.isEmpty();
    }
}

C++版：

class Solution {
public:
	bool isValid(string s) {
		stack<char> stack;

		// 遍历字符串中的每个字符
		for (char& c : s) {
			// 如果是左括号，推入栈中
			if (c == '(' || c == '{' || c == '[') {
				stack.push(c);
			}
			else {
				// 如果栈为空，则没有对应的左括号可以匹配当前右括号
				if (stack.empty()) {
					return false;
				}

				// 检查栈顶元素与当前右括号是否匹配
				char top = stack.top();
				stack.pop();
				if ((c == ')' && top != '(') || (c == '}' && top != '{') || (c == ']' && top != '[')) {
					return false;
				}
			}
		}

		// 如果栈为空，则所有左括号都成功匹配了对应的右括号
		return stack.empty();
	}
};

C版：

// 模拟栈的结构体
typedef struct {
	char* elements; // 栈元素数组
	int top;        // 栈顶索引
	int maxSize;    // 栈的最大容量
} Stack;

// 初始化栈
void initStack(Stack* stack, int size) {
	stack->elements = (char*)malloc(size * sizeof(char));
	stack->top = -1;
	stack->maxSize = size;
}

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

// 向栈中压入元素
void push(Stack* stack, char element) {
	if (stack->top < stack->maxSize - 1) {
		stack->elements[++stack->top] = element;
	}
}

// 从栈中弹出元素
void pop(Stack* stack) {
	if (stack->top != -1) {
		stack->top--;
	}
}

// 获取栈顶元素
char top(Stack* stack) {
	if (stack->top != -1) {
		return stack->elements[stack->top];
	}
	return '\0'; // 返回空字符表示栈为空
}

// 判断字符串是否为有效的括号序列
int isValid(char* s) {
	int length = strlen(s);
	Stack stack;
	initStack(&stack, length);

	for (int i = 0; i < length; i++) {
		char c = s[i];

		// 如果是左括号，压入栈中
		if (c == '(' || c == '{' || c == '[') {
			push(&stack, c);
		}
		else {
			// 如果是右括号，检查栈是否为空或栈顶元素是否与之匹配
			if (isEmpty(&stack)) {
				return 0; // 栈为空，括号序列无效
			}

			char topElement = top(&stack);
			if ((c == ')' && topElement != '(') || (c == '}' && topElement != '{') || (c == ']' && topElement != '[')) {
				return 0; // 不匹配，括号序列无效
			}

			pop(&stack); // 弹出栈顶元素
		}
	}

	int isValid = isEmpty(&stack); // 如果栈为空，则括号序列有效
	free(stack.elements); // 释放栈元素数组的内存
	return isValid;
}