[力扣_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;
}

本文链接：