Leetcode 20 - Valid Parentheses
| String | Stack |
Leetcode Link for Valid Parentheses
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
Constraints:
1 <= s.length <= 104
s consists of parentheses only ‘()[]{}’
Solution:
public boolean isValid(String s) {
if(s.length()==1)
return false;
Deque<Character> stack = new ArrayDeque<>();
for(char c : s.toCharArray()){
if(c == '(' || c == '{' || c=='['){
stack.push(c);
}
else{
if(stack.isEmpty())
return false;
char inStack = stack.pop();
if(c == ')' && inStack != '(')
return false;
if(c == '}' && inStack != '{')
return false;
if(c == ']' && inStack != '[')
return false;
}
}
return stack.isEmpty();
}
Github Link: https://github.com/miqbal3636/problem_solving/blob/main/src/com/spsoft/leetcode/medium/stack/L20ValidParentheses.java
Methodology:
- Initial Check:
If the string length is 1, it immediately returns false as a single character cannot be a valid combination of brackets.
- Stack Initialization:
A stack (Deque
- Iteration through Characters:
For each character c in the string:
If c is an opening bracket ((, {, [), it is pushed onto the stack.
If c is a closing bracket (), }, ]):
The function checks if the stack is empty. If it is, it returns false.
It then pops the top element from the stack and checks if this matches the corresponding opening bracket for c. If it doesn’t match, the function returns false.
- Final Check:
After iterating through all characters, the function returns true if the stack is empty (indicating all opening brackets were matched with closing brackets), otherwise it returns false.
Time complexity: 𝑂(𝑛) where 𝑛 is the length of the string
Space complexity: 𝑂(𝑛) due to the stack.
Author: Mohammad J Iqbal
