20 LeetCode problem solution
LeetCode problem link: 20. Valid Parentheses
LeetCode 20. Valid Parentheses problem description
Easy level problem.
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
Example 4:
Input: s = "([])"
Output: true
Example 5:
Input: s = "([)]"
Output: false
Constraints:
1 <= s.length <= 104sconsists of parentheses only'()[]{}'.
LeetCode 20. Valid Parentheses problem solution
This is a classic problem for using a Stack data structure to keep track of opening brackets.
When we see an opening bracket, push it onto the stack. When we see a closing bracket, the top of the stack must contain its matching opening bracket. If the stack is empty or the brackets do not match, return false.
After processing the entire string, the stack must be empty. Otherwise, some opening brackets were never closed.
Patterns | Techniques | Data Structures
Stack - data structure
Bracket Matching - technique
Complexity
Time complexity: O(n)
We process each character exactly once. Each bracket is pushed onto the stack at most once and popped at most once, and both stack operations take O(1) time.
Therefore, the total time complexity is O(n).
Space complexity: O(n)
In the worst case, the string contains only opening brackets, for example (((([[{{
All of them are stored in the stack, so the stack can contain up to n elements.
Therefore, the space complexity is O(n).
LeetCode 20. Valid Parentheses problem example
s = "({[]})"Start with an empty stack:
stack = []Step 1:
( is an opening bracket, so push it onto the stack.
stack = ['(']Step 2:
{ is an opening bracket, so push it onto the stack.
stack = ['(', '{']Step 3:
[ is an opening bracket, so push it onto the stack.
stack = ['(', '{', '[']Step 4:
] is a closing bracket.
The top of the stack is [, which is the matching opening bracket for ].
Pop [ from the stack.
stack = ['(', '{']Step 5:
} is a closing bracket.
The top of the stack is {, which matches }.
Pop { from the stack.
stack = ['(']Step 6:
) is a closing bracket.
The top of the stack is (, which matches ).
Pop ( from the stack.
stack = []The stack is empty after processing all characters, so every opening bracket was closed in the correct order.
Result is true.
LeetCode 20 C++ solution
class Solution {
public:
bool isValid(string s) {
stack<char> st;
for(char c : s)
{
// Store opening brackets.
if(c == '(' || c == '{' || c == '[')
{
st.push(c);
continue;
}
// A closing bracket cannot be matched
// if there is no opening bracket.
if(st.empty()) return false;
char top = st.top();
// Check whether the closing bracket
// matches the latest opening bracket.
if((c == ')' && top != '(') || (c == '}' && top != '{') || (c == ']' && top != '['))
{
return false;
}
// The pair is valid, remove the opening bracket.
st.pop();
}
// No unmatched opening brackets should remain.
return st.empty();
}
};LeetCode 20 Java solution
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for(char c : s.toCharArray()) {
// Store opening brackets.
if(c == '(' || c == '{' || c == '[') {
stack.push(c);
continue;
}
// A closing bracket cannot be matched
// if there is no opening bracket.
if(stack.isEmpty()) {
return false;
}
char top = stack.peek();
// Check whether the closing bracket
// matches the latest opening bracket.
if((c == ')' && top != '(') || (c == '}' && top != '{') || (c == ']' && top != '[')) {
return false;
}
// The pair is valid, remove the opening bracket.
stack.pop();
}
// No unmatched opening brackets should remain.
return stack.isEmpty();
}
}LeetCode 20 JavaScript solution
var isValid = function(s) {
const stack = [];
for(const c of s) {
// Store opening brackets.
if(c === '(' || c === '{' || c === '[') {
stack.push(c);
continue;
}
// A closing bracket cannot be matched
// if there is no opening bracket.
if(stack.length === 0) {
return false;
}
const top = stack[stack.length - 1];
// Check whether the closing bracket
// matches the latest opening bracket.
if((c === ')' && top !== '(') || (c === '}' && top !== '{') || (c === ']' && top !== '[')) {
return false;
}
// The pair is valid, remove the opening bracket.
stack.pop();
}
// No unmatched opening brackets should remain.
return stack.length === 0;
};LeetCode 20 TypeScript solution
function isValid(s: string): boolean {
const stack: string[] = [];
for(const c of s) {
// Store opening brackets.
if(c === '(' || c === '{' || c === '[') {
stack.push(c);
continue;
}
// A closing bracket cannot be matched
// if there is no opening bracket.
if(stack.length === 0) {
return false;
}
const top = stack[stack.length - 1];
// Check whether the closing bracket
// matches the latest opening bracket.
if((c === ')' && top !== '(') || (c === '}' && top !== '{') || (c === ']' && top !== '[')) {
return false;
}
// The pair is valid, remove the opening bracket.
stack.pop();
}
// No unmatched opening brackets should remain.
return stack.length === 0;
}LeetCode 20 Python solution
class Solution:
def isValid(self, s: str) -> bool:
stack = []
for c in s:
# Store opening brackets.
if c in "({[":
stack.append(c)
continue
# A closing bracket cannot be matched
# if there is no opening bracket.
if not stack:
return False
top = stack[-1]
# Check whether the closing bracket
# matches the latest opening bracket.
if ((c == ')' and top != '(') or (c == '}' and top != '{') or (c == ']' and top != '[')):
return False
# The pair is valid, remove the opening bracket.
stack.pop()
# No unmatched opening brackets should remain.
return not stack