1.题目描述
OJ链接 【leetcode 题号：20.有效的括号】【难度：简单】
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
提示：
1 <= s.length <= 104s仅由括号'()[]{}'组成
2.解题思路+代码实现
方法：栈
思路及算法：
判断括号的有效性可以使用「栈」这一数据结构来解决。
我们遍历给定的字符串s。当我们遇到一个左括号时，我们会期望在后续的遍历中，有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合，因此我们可以将这个左括号放入栈顶。
当我们遇到一个右括号时，我们需要将一个相同类型的左括号闭合。此时，我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型，或者栈中并没有左括号，那么字符串s无效，返回False。为了快速判断括号的类型，我们可以使用哈希表存储每一种括号。哈希表的键为右括号，值为相同类型的左括号。
在遍历结束后，如果栈中没有左括号，说明我们将字符串s中的所有左括号闭合，返回True，否则返回False。
注意到有效字符串的长度一定为偶数，因此如果字符串的长度为奇数，我们可以直接返回False，省去后续的遍历判断过程。
代码实现：
typedef char STDataType; typedef struct Stack { STDataType* a; int top; int capacity; }ST; void STInit(ST* pst) { assert(pst); pst->a = NULL; pst->top = 0; pst->capacity = 0; } void STDestroy(ST* pst) { assert(pst); free(pst->a); pst->a = NULL; pst->top = 0; pst->capacity = 0; } void STPush(ST* pst,STDataType x) { if (pst->top == pst->capacity) { int newCapacity = pst->capacity == 0 ? 4 :pst-> capacity * 2; STDataType* tmp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType)); if (tmp == NULL) { perror("realloc fail"); return; } pst->a = tmp; pst->capacity = newCapacity; } pst->a[pst->top] = x; pst->top++; } bool STEmpty(ST* pst) { assert(pst); return pst->top == 0; } void STPop(ST* pst) { assert(pst); assert(!STEmpty(pst)); pst->top--; } STDataType STTop(ST* pst) { assert(pst); assert(!STEmpty(pst)); return pst->a[pst->top - 1]; } int STSize(ST* pst) { assert(pst); return pst->top; } bool isValid(char* s) { ST st; STInit(&st); while (*s) { if (*s == '(' || *s == '[' || *s == '{') { STPush(&st, *s); } else { if (STEmpty(&st)) { STDestroy(&st); return false; } char top = STTop(&st); STPop(&st); if ((top != '(' && *s == ')') || (top != '{' && *s == '}') || (top != '[' && *s == ']')) { STDestroy(&st); return false; } } s++; } bool ret = STEmpty(&st); STDestroy(&st); return ret; }
复杂度分析
- 时间复杂度：O(n)，其中n是字符串 sss 的长度。
- 空间复杂度：O(n+∣Σ∣)，其中 Σ\SigmaΣ 表示字符集，本题中字符串只包含 666 种括号，∣Σ∣=6。栈中的字符数量为 O(n)，而哈希表使用的空间为O(∣Σ∣)，相加即可得到总空间复杂度。
