首页 > 代码库 > 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.

分析:一个很简单的想法是用栈保存左括号。时间复杂度O(n), 空间复杂度O(n)。

class Solution {public:    bool isValid(string s) {        int n = s.length();        if(n == 0) return true;                stack<char> S;        for(int i = 0; i < n; i++){            if(s[i] == ( || s[i] == { || s[i] == [)                S.push(s[i]);            else if(!S.empty() && match(S.top(), s[i]))                    S.pop();            else return false;        }                return S.empty();    }        bool match(char l, char r){        return l == ( && r == ) || l == { && r == } || l == [ && r == ];    }};

 

Leetcode: Valid Parentheses