Leetcode 20 有效的括号valid-parentheses(…

2018-09-18 06:25:16来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

给定一个只包括 '('')''{''}''['']' 的字符串,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

=============================================================
基本思路其实还是比较简单的, 我刚刚开始想得就十分的复杂。。。
首先分析一下:
  1. 左括号必须有右括号匹配,并且与其匹配的括号是同类型的;
  2. 不同类型的括号不能穿插含括,如例4,存在线性规则。

 

毫无疑问要使用栈了(虽然我看到了栈的标签了ehahaha...) 

 

由上面的特性就可以得到基本思路

        碰到左括号则压入栈中;

        碰到右括号,则与栈顶进行匹配,如果属于同类型,则把栈顶弹出(注意监测空栈),如果不同,return false;

        最后监测空栈,不是空栈(有括号剩余),return false;

        是空栈,return ture;

 

下面是AC代码:

 1 class Solution {
 2 public:
 3     bool isValid(string s) {
 4         stack <char> mark;
 5         for(char temp :s){
 6             if (temp=='(')
 7                 mark.push(')');
 8             else if(temp=='[')
 9                 mark.push(']');
10             else if(temp=='{')
11                 mark.push('}');
12             else{
13                 if (mark.empty()||temp!=mark.top())
14                     return false;      
15                 else mark.pop();
16             }
17         }
18         return mark.empty();
19         }              
20 };

 


 
 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:引用

下一篇:cf1042F. Leaf Sets(贪心)