首页 > 代码库 > 【leetcode】Valid Parentheses

【leetcode】Valid Parentheses

Given a string containing just the characters ‘(‘‘)‘‘{‘‘}‘‘[‘ and ‘]‘, determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

 

思路,用栈。之前做过,现在写的更简洁了。 从后向前遍历string,遇到右括号就压栈,遇到匹配的左括号就弹栈,如果遇到不匹配的左括号,那就有错,最后栈空则有效。

class Solution {public:    bool isValid(string s) {        vector<char> vec;        for(int i = s.length() - 1; i >= 0; i--)        {            if(s[i] == ) || s[i] == ] || s[i] == })            {                vec.push_back(s[i]);            }            else if(s[i] == ( && !vec.empty() && vec.back() == ))            {                vec.pop_back();            }            else if(s[i] == [ && !vec.empty() && vec.back() == ])            {                vec.pop_back();            }            else if(s[i] == { && !vec.empty() && vec.back() == })            {                vec.pop_back();            }            else            {                return false;            }        }        return vec.empty();    }};

 

【leetcode】Valid Parentheses