leetcode_20_ValidParentheses

阅读数:0次 2019-06-13

× 文章目录

1. 题目描述
2. 思路
3. 代码

题目描述

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。示例

1 2	1:输入: "()" 输出: true

示例 2:

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

示例 3:

1
2
3

输入: "(]"
输出: false
`

示例 4:

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

示例 5:

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

思路

用栈保存未匹配的括号；
当获取到的是左括号时直接进栈；
如果是右括号，判断栈是否为空，如果为空则一定不匹配；
如果是右括号，栈非空，则判断栈顶元素是否和当前获取的元素相匹配。
在字符串遍历结束时如果循环过程中没有直接返回，判断栈是否清空，如果清空了则代表所有字符都匹配了，如果没有则未完全匹配。

代码

class Solution {
public:
    bool isValid(string s) {
        stack<char> t;
       for(int i=0;i<s.length();i++)
       {
           if(s[i] == ')' || s[i] == ']' || s[i] == '}')
           {    
               // 思路3
               if (t.empty())
                   return false;
               else 
               // 思路4
               {
                   if(s[i] == ')' && t.top() != '(')
                       return false;
                   else if(s[i] == ']' && t.top() != '[')
                       return false;
                   else if(s[i] == '}' && t.top() != '{')
                       return false;
                   else 
                       t.pop();
               }
           }
           else
           {
               //思路2
               t.push(s[i]);
           }
       }
       //思路5
        return t.empty();
        
    }
};

通过后看了别人的题解，发现可以提前判断下字符串长度，如果是奇数则可以直接认定不匹配。

转载请注明作者及出处,本文作者为李志伟,本文标题为leetcode_20_ValidParentheses 本文链接为http://www.lizhiwei.net/leetcode-20-ValidParentheses.html