# LeetCode题目：Valid Parentheses

By | 2012 年 11 月 6 日

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.

## Solutions

### Ruby

```MAP = {
'}' => '{',
']' => '[',
')' => '('
}
CLOSINGS = MAP.keys
OPENINGS = MAP.values
def is_valid(s)
stack = []
s.each_char do |c|
if CLOSINGS.include?(c)
return false if stack.size == 0 || stack.pop != MAP[c]
elsif OPENINGS.include?(c)
stack.push(c)
end
end
stack.size == 0
end
```

### C++, 8ms过大集合

```class Solution {
public:
bool isValid(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
stack<char> lefts;
for(int i = 0 ; i < s.size() ;++i) {
char c = s[i];
if(c == '(' || c == '[' || c == '{') {
lefts.push(c);
} else {
if (lefts.size() == 0) return false;
char top = lefts.top();
if (c == ')') {
if(top != '(') return false;
} else if ( c == ']' ) {
if(top != '[') return false;
} else if ( c == '}' ){
if(top != '{') return false;
}
lefts.pop();
}
}
return lefts.size() == 0;
}
};
```