Valid Parentheses
Post
Cancel

# LeetCode #20: Valid Parentheses (C/C++).

easy

source: https://leetcode.com/problems/valid-parentheses
C/C++ Solution to LeetCode problem 20. Valid Parentheses.

## Problem

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

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

## Examples

Input: s = “()”
Output: true

### Example 2:

Input: s = “()[]{}”
Output: true

Input: s = “(]”
Output: false

## Constraints

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

## Solution

Using stack:

• If the string length is odd, return false.
• For every character:
• If is an open parentheses, push to the stack.
• If is a close parentheses:
• If stack is empty, return false.
• Pop from stack and verify if the close parentheses corresponds to the open one (the one poped).
• If not, return false.
• Once finish, if the stack is empty, return true, otherwise false.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { public: bool isValid(string s) { if (s.size() % 2 != 0) return false; unordered_map<char, char> m; stack<char> st; m[')'] = '('; m['}'] = '{'; m[']'] = '['; for (int i=0; i<s.size(); i+=1) { if (s[i] == '(' || s[i] == '{' || s[i] == '[') { st.push(s[i]); } else { if (st.empty() || st.top() != m[s[i]]) return false; st.pop(); } } return st.empty(); } };