【LeetCode刷题日志】20.有效的括号

雨点打透心脏的1/2处 2024-04-22 04:36 97阅读 0赞

![aa51d19831f844e4a87c9a41f570d7f6.png][]

>  *  ?个人主页：[库库的里昂][Link 1]
>  *  ?C/C++领域新星创作者
>  *  ?欢迎 ?点赞✍评论⭐收藏
>  *  ✨收录专栏：[LeetCode 刷题日志][LeetCode]
>  *  ?希望作者的文章能对你有所帮助，有不足的地方请在评论区留言指正，大家一起学习交流！?

**目录**

1.题目描述

2.解题思路+代码实现

方法：栈

思路及算法：

代码实现：

--------------------

#### 1.题目描述 ####

[OJ链接][OJ] 【[leetcode][] 题号：20.有效的括号】【难度：简单】

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

有效字符串需满足：

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

**示例 1：**

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

**示例 2：**

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

**示例 3：**

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

**提示：**

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

#### 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(∣Σ∣)，相加即可得到总空间复杂度。

![7ba13d96bef5407c8fae4224089bbd9e.png][]

[aa51d19831f844e4a87c9a41f570d7f6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/0d0a4d7cdea546caaf2f5cd137eb82b7.png
[Link 1]: https://blog.csdn.net/m0_68662723
[LeetCode]: http://t.csdnimg.cn/j5fPj
[OJ]: https://leetcode.cn/problems/valid-parentheses/
[leetcode]: https://so.csdn.net/so/search?q=leetcode&spm=1001.2101.3001.7020
[7ba13d96bef5407c8fae4224089bbd9e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/c280f6a5a1914ae6bf5576db63626ad5.png