【力扣刷题实战】有效的括号
大家好,我是小卡皮巴拉
文章目录
目录
力扣题目: 有效的括号
题目描述
示例 1:
示例 2:
示例 3:
示例 4:
解题思路
问题理解
算法选择
具体思路
解题要点
完整代码(C语言)
兄弟们共勉 !!!
每篇前言
博客主页:小卡皮巴拉
咱的口号:🌹小比特,大梦想🌹
作者请求:由于博主水平有限,难免会有错误和不准之处,我也非常渴望知道这些错误,恳请大佬们批评斧正。
力扣题目: 有效的括号
原题链接:有效的括号
题目描述
给定一个只包括
'('
,')'
,'{'
,'}'
,'['
,']'
的字符串s
,判断字符串是否有效。有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例 1:
输入:s = "()"
输出:true
示例 2:
输入:s = "()[]{}"
输出:true
示例 3:
输入:s = "(]"
输出:false
示例 4:
输入:s = "([])"
输出:true
解题思路
问题理解
题目要求我们判断一个仅包含括号('(',')','{','}','[',']')的字符串是否有效。有效字符串需满足以下条件:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
算法选择
我们可以使用栈(Stack)这一数据结构来解决这个问题。栈的特点是后进先出(LIFO),非常适合处理这种需要匹配和回溯的问题。
具体思路
初始化栈:首先,我们需要一个栈来存储左括号。在C语言中,我们可以定义一个栈的数据结构
ST
,并初始化它。遍历字符串:使用指针
pi
遍历输入的字符串s
。处理左括号:如果当前字符是左括号('('、'{'、'['),则将其压入栈中。
处理右括号:
首先检查栈是否为空。如果为空,说明没有对应的左括号来匹配当前的右括号,因此字符串无效。
如果栈不为空,取出栈顶元素(即最近入栈的左括号),并检查它是否与当前的右括号匹配。
如果不匹配,或者栈顶元素不是对应的左括号,则字符串无效。
如果匹配,则弹出栈顶元素(即移除已匹配的左括号)。
遍历结束后检查:遍历完整个字符串后,检查栈是否为空。如果为空,说明所有左括号都得到了正确匹配和闭合,字符串有效;否则,字符串无效。
销毁栈:在返回结果之前,销毁栈以释放分配的内存。
解题要点
栈的使用:用于存储左括号,并在遇到右括号时弹出栈顶元素进行匹配。
括号匹配:使用哈希表或数组来快速判断右括号是否与栈顶的左括号匹配。
遍历结束后的检查:遍历结束后,栈应为空,否则说明有未匹配的左括号。
完整代码(C语言)
typedef char STDataType; //定义栈的数据结构 typedef struct Stack { STDataType* arr; int top;//指向栈顶位置 int capacity; }ST; //初始化 void STInit(ST* ps) { assert(ps); ps->arr = NULL; ps->top = ps->capacity = 0; } //销毁 void STDestroy(ST* ps) { if (ps->arr != NULL) free(ps->arr); ps->arr = NULL; ps->capacity = ps->top = 0; } //入栈——栈顶 void StackPush(ST* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity) { //空间满了,增容 int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType)); if (tmp == NULL) { perror("realloc fail!\n"); exit(1); } ps->arr = tmp; ps->capacity = newCapacity; } //空间足够 ps->arr[ps->top++] = x; } //栈是否为空 bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } //出栈——栈顶 void StackPop(ST* ps) { assert(!StackEmpty(ps)); ps->arr[(ps->top)--]; } //取栈顶元素 STDataType StackTop(ST* ps) { assert(!StackEmpty(ps)); return ps->arr[ps->top - 1]; } bool isValid(char* s) { //借助数据结构——栈,遇到左括号就入栈,遇到右括号就取栈顶元素检查是否是与之对应的右括号 ST st; STInit(&st); char* pi = s; while(*pi != '\0') { if(*pi == '(' || *pi == '{' || *pi == '[') { //入栈 StackPush(&st,*pi); }else { //取栈顶,判断 if(StackEmpty(&st)) return false; char top = StackTop(&st); if((top =='('&& *pi != ')') ||(top == '['&& *pi !=']') ||(top == '{'&& *pi != '}')) return false; StackPop(&st); } pi++; } bool ret = StackEmpty(&st) ? true:false; STDestroy(&st); return ret; }
兄弟们共勉 !!!
码字不易,求个三连
抱拳了兄弟们!