你好，欢迎来到我的博客！作为一名程序员，我经常刷LeetCode题目来提升自己的编程能力。在我的博客里，我会分享一些我自己做过的题目和解题思路，希望能够帮助到大家。今天，我想和大家分享一道挑战性较高的题目，让我们一起来挑战一下吧！作者也是在学习的过程中刷到有意思的题目就会选择与大家分享，并且提供较优解，关于力扣的文章全部放在博客，如果大家喜欢记得支持作者。🤓
题目难度：简单
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 3.每个右括号都有一个对应的相同类型的左括号。
示例一：
输入：s = “()[]{}”
输出：true
示例二：
输入：s = “(]”
输出：false
示例三：
输入：s = “([{}])”
输出：true
解题思路💡
总结：题目叫我们对有效括号字符串进行判断，大概意思为，字符串输入完成后，必须保证字符串内括号全部匹配上（要求参考题目与示例），我们可以选择使用栈来存储左括号，因为最后进入的左括号会被最先拿出去匹配，符合题意按顺序闭合，要是发现有不匹配直接返回false。（接下来带来两种使用栈的解法）
本题可以说是标准的栈练习题了，如果使用C++会非常简单因为直接调用栈库函数即可，使用C语言需要手写一个栈（如果不了解栈的小伙伴们可以点击跳转）。
匹配成功示例
匹配成功示例
解题步骤
（第一步）
- 写出一个
栈，有基本的初始化、入栈、出栈、销毁等常用栈功能，方便后续调用。
（第二步）
- 对字符串s进行遍历
（第三步）
- 遍历字符串s，将左括号放栈中，右括号与栈顶的左括号进行匹配，匹配不成功返回false，如果字符为右括号时栈为空则直接返回false，遍历到字符串的结尾没有出现匹配失败且栈为空则返回true。
解法一⭐
typedef char STDataType; typedef struct STNode //栈结构体 { STDataType* str; int top; int capacity; }STNode; void STInit(STNode* pst) { assert(pst); pst->str = NULL; pst->top = 0; pst->capacity = 0; } bool STEmpty(STNode* pst) { assert(pst); return pst->top == 0; } void STPush(STNode* pst, STDataType data) { assert(pst); if (pst->top == pst->capacity) { int Newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; STDataType* temp = (STDataType*)realloc(pst->str,sizeof(STDataType) * Newcapacity); if (temp == NULL) { perror("malloc error"); return; } pst->str = temp; pst->capacity = Newcapacity; } pst->str[pst->top++] = data; } void STPop(STNode* pst) { assert(pst); assert(!STEmpty(pst)); pst->top--; } void STDestroy(STNode* pst) { assert(pst); free(pst->str); pst->top = 0; pst->capacity = 0; } STDataType STTop(STNode* pst) { assert(pst); assert(!STEmpty(pst)); return pst->str[pst->top - 1]; } bool isValid(char* s) { STNode pst; STInit(&pst); while (*s) { if (*s == '(' || *s == '[' || *s == '{') { STPush(&pst, *s); } else { if (STEmpty(&pst)) return false; if ((STTop(&pst) == '(' && *s != ')') || (STTop(&pst) == '[' && *s != ']') || (STTop(&pst) == '{' && *s != '}')) { return false; } else { STPop(&pst); } } s++; } return STEmpty(&pst); }
解法二🌈(更优解)
其实这种解法也是使用栈的形式，只不过用数组来模拟栈来操作。
解题步骤：
- 定义一个数组来装字符串，并且定义一个top当作栈顶
- 遍历字符串，左括号放在数组里，匹配到右括号与栈顶元素进行匹配，全部匹配成功返回true，匹配失败返回false，如果遍历到右括号时数组中没有左括号直接返回false
bool isValid(char * s) { char a[10000]=" ",t; int i=0,top=0; while(s[i]!='\0') { if(s[i]=='('||s[i]=='{'||s[i]=='[') { if(s[i]=='(') t=')'; if(s[i]=='{') t='}'; if(s[i]=='[') t=']'; top++; a[top]=t; } else { if(a[top]!=s[i]) return false; else top--; } i++; } if(top==0) return true; else return false; }
完结
当你喜欢一篇文章时，点赞、收藏和关注是最好的支持方式。如果你喜欢我的文章，请不要吝啬你的支持，点赞👍、收藏⭐和关注都是对我最好的鼓励。感谢你们的支持！
