[力扣_20] 有效的括号

题目入口:点击进入

相关算法:

  • 栈的应用——时间复杂度O(n),n为字符串的长度,空间复杂度O(主要是栈的开销)

思路和算法:

这道题我们之前栈和对列中的题解讲过,就是一个栈的基本应用,我们可以将所有左括号入栈,然后遇到右括号的时候再弹出栈顶元素去判断是否匹配,如不匹配则直接返回false,会出现以下情况:

  • 字符串未遍历完而栈为空时,返回false,右括号过多
  • 字符串遍历完而栈不空时,返回false,左括号过多

若未出现以上情况,则返回true,当字符串为空时,应题意,返回true

动图如下所示:

img

img

img

img

img

img

img

代码如下所示:

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;
}

本文链接:

https://nullcode.fun/66.html
1 + 8 =
快来做第一个评论的人吧~