Valid Parentheses
Program for Valid Parentheses in an Expression Problem
You are given a string s containing the characters (, ), {, }, [, and ].
The string s is considered valid if it meets the following conditions:
- Every opening bracket has a corresponding closing bracket of the same type.
- Opening brackets are closed in the correct order.
- Every closing bracket has a matching opening bracket of the same type.
Your task is to determine whether the string s is valid. Return true if it is valid, and false otherwise.
Output: true
Output: true
Output: false
Explanation :
The brackets are not closed in the correct order.
Constraints:
- 1 <= s.length <= 1000
Program for Valid Parentheses in an Expression Solution
Recommendation for Time and Space Complexity – You should aim for a solution with O(n) time and O(n) space, where n is the length of the given string.
Hints for solving problems
Hint 1 :
A brute force solution would be to continuously remove valid brackets until no more can be removed. If the remaining string is empty, return true; otherwise, return false. This would result in an O(n^2) solution. Can we think of a better approach? Perhaps a data structure could help.
Hint 2 :
We can use a stack to store characters. Iterate through the string by index. For an opening bracket, push it onto the stack. If the bracket is a closing type, check for the corresponding opening bracket at the top of the stack. If we don’t find the corresponding opening bracket, immediately return false. Why does this work?
There are mainly 2 approach to solve this problem-
- Brute Force Method
- Stack Method
1. Brute Force Method
Continuously replace valid pairs of parentheses ((), {}, []) in the string until no more replacements can be made. If the string becomes empty, it is valid; otherwise, it is not. This method is simple but inefficient with a time complexity of O(n^2).
- Time complexity: O(n^2)
- Space complexity: O(n)
Code
class Solution {
public:
bool isValid(string s) {
while (true) {
size_t pos = string::npos;
if ((pos = s.find("()")) != string::npos) {
s.erase(pos, 2);
continue;
}
if ((pos = s.find("{}")) != string::npos) {
s.erase(pos, 2);
continue;
}
if ((pos = s.find("[]")) != string::npos) {
s.erase(pos, 2);
continue;
}
break;
}
return s.empty();
}
};
public class Solution {
public boolean isValid(String s) {
while (s.contains("()") || s.contains("{}") || s.contains("[]")) {
s = s.replace("()", "");
s = s.replace("{}", "");
s = s.replace("[]", "");
}
return s.isEmpty();
}
}
class Solution:
def isValid(self, s: str) -> bool:
while '()' in s or '{}' in s or '[]' in s:
s = s.replace('()', '')
s = s.replace('{}', '')
s = s.replace('[]', '')
return s == ''
class Solution {
/**
* @param {string} s
* @return {boolean}
*/
isValid(s) {
while (s.includes("()") || s.includes("{}") || s.includes("[]")) {
s = s.replace("()", "");
s = s.replace("{}", "");
s = s.replace("[]", "");
}
return s === "";
}
}
2. Stack Method
Use a stack to track opening brackets as they appear. For each closing bracket, check if it matches the top of the stack; if not, the string is invalid. If the stack is empty at the end, the string is valid. This approach is efficient with a time complexity of O(n)
- Time complexity: O(n)
- Space complexity: O(n)
Code
class Solution {
public:
bool isValid(string s) {
std::stack stack;
std::unordered_map closeToOpen = {
{')', '('},
{']', '['},
{'}', '{'}
};
for (char c : s) {
if (closeToOpen.count(c)) {
if (!stack.empty() && stack.top() == closeToOpen[c]) {
stack.pop();
} else {
return false;
}
} else {
stack.push(c);
}
}
return stack.empty();
}
};
public class Solution {
public boolean isValid(String s) {
Stack stack = new Stack<>();
java.util.Map closeToOpen = new java.util.HashMap<>();
closeToOpen.put(')', '(');
closeToOpen.put(']', '[');
closeToOpen.put('}', '{');
for (char c : s.toCharArray()) {
if (closeToOpen.containsKey(c)) {
if (!stack.isEmpty() && stack.peek() == closeToOpen.get(c)) {
stack.pop();
} else {
return false;
}
} else {
stack.push(c);
}
}
return stack.isEmpty();
}
}
class Solution:
def isValid(self, s: str) -> bool:
stack = []
closeToOpen = { ")" : "(", "]" : "[", "}" : "{" }
for c in s:
if c in closeToOpen:
if stack and stack[-1] == closeToOpen[c]:
stack.pop()
else:
return False
else:
stack.append(c)
return True if not stack else False
class Solution {
/**
* @param {string} s
* @return {boolean}
*/
isValid(s) {
const stack = [];
const closeToOpen = {
')': '(',
']': '[',
'}': '{'
};
for (let c of s) {
if (closeToOpen[c]) {
if (stack.length > 0 && stack[stack.length - 1] === closeToOpen[c]) {
stack.pop();
} else {
return false;
}
} else {
stack.push(c);
}
}
return stack.length === 0;
}
}
