[力扣_20] 有效的括号
题目入口:点击进入
相关算法:
- 栈的应用——时间复杂度O(n),n为字符串的长度,空间复杂度O(主要是栈的开销)
思路和算法:
这道题我们之前栈和对列中的题解讲过,就是一个栈的基本应用,我们可以将所有左括号入栈,然后遇到右括号的时候再弹出栈顶元素去判断是否匹配,如不匹配则直接返回false,会出现以下情况:
- 字符串未遍历完而栈为空时,返回false,右括号过多
- 字符串遍历完而栈不空时,返回false,左括号过多
若未出现以上情况,则返回true,当字符串为空时,应题意,返回true
动图如下所示:
代码如下所示:
bool isValid(char * s){
if(!s) return true;
if(s[1]=='\0') return false;
int sleng=strlen(s);
char *Stack=(char*)malloc(sizeof(char)*(sleng+1));
int index=0;
char temp;
for(int i=0;i<sleng;i++)
{
if(s[i]=='('||s[i]=='['||s[i]=='{')
{
Stack[index]=s[i];
index++;
}
else if(index>0)
{
index--;
temp=Stack[index];
if(s[i]==')'){
if(temp!='(')
return false;
}
else if(s[i]==']'){
if(temp!='[')
return false;
}
else if(s[i]=='}'){
if(temp!='{')
return false;
}
}
else{
return false;
}
}
if(index>0) return false;
return true;
}