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.
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'()[]{}'.
Approach 01: Stack
class Solution {
public:
bool isValid(string s) {
stack st;
for (char c : s) {
if (c == '(' || c == '{' || c == '[') {
st.push(c);
} else {
if (st.empty()) return false;
if (c == ')' && st.top() != '(') return false;
if (c == '}' && st.top() != '{') return false;
if (c == ']' && st.top() != '[') return false;
st.pop();
}
}
return st.empty();
}
};
Time Complexity:
- O(n): Single pass through the string.
Space Complexity:
- O(n): In the worst case, the stack stores all characters.
class Solution:
def isValid(self, s: str) -> bool:
stack = []
mapping = {")": "(", "}": "{", "]": "["}
for char in s:
if char in mapping:
top_element = stack.pop() if stack else '#'
if mapping[char] != top_element:
return False
else:
stack.append(char)
return not stack
Time Complexity:
- O(n): Single pass through the string.
Space Complexity:
- O(n): In the worst case, the stack stores all characters.
class Solution {
public boolean isValid(String s) {
Stack stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
} else {
if (stack.isEmpty()) return false;
char top = stack.pop();
if (c == ')' && top != '(') return false;
if (c == '}' && top != '{') return false;
if (c == ']' && top != '[') return false;
}
}
return stack.isEmpty();
}
}
Time Complexity:
- O(n): Single pass through the string.
Space Complexity:
- O(n): In the worst case, the stack stores all characters.