Category : Easy
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.
leetcode.com/problems/valid-parentheses/
Examples:
Example 1
1 2 | Input: s = "()" Output: true |
Example 2
1 2 | Input: s = "()[]{}" Output: true |
Example 3
1 2 | Input: s = "(]" Output: false |
Example 4
1 2 | Input: s = "([)]" Output: false |
Example 5
1 2 | Input: s = "{[]}" Output: true |
Constraints:
1 <= s.length <= 104sconsists of parentheses only'()[]{}'.
Solution Approach
For this problem of valid parenthesis, we need a data structure that is capable of containing many characters and which removes the top element whenever the match of the same type of bracket is found that is we need to enter the data in first in first out manner. Therefore, the stack will be the best data structure for this problem.
In the stack, we will first keep adding all the character if they are opening braces, irrespective of its type. If we encounter any closing brace then we will check if that compliments the brace at the top of the stack. In case the complement is present, then we will just remove the top element of the stack. If the complement is not present at the top of the stack then we straight away return false. We also return false when there is nothing in the stack and there is an incoming closing brace of any type. At the end when we go through the complete string and if there is anything present in the stack we return false and if nothing is present in it and all are above conditions are met then we return true from our function.
Solution Code
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | class Solution { public boolean isValid(String s) { Stack<Character> stack = new Stack<>(); for (char ch: s.toCharArray()) { if ((ch == '{') || (ch == '(') || (ch=='[')){ stack.push(ch); } if(stack.size()>0) { if(ch == '}'){ if (stack.peek() == '{'){ stack.pop(); } else return false; } else if(ch == ')'){ if (stack.peek() == '('){ stack.pop(); } else return false; } else if(ch == ']'){ if (stack.peek() == '['){ stack.pop(); } else return false; } } else return false; } if (stack.size()>0) return false; return true; } } |
For more Leetcode explained solutions visit Leetcode Solutions. If you like capture the flag challenges visit here.
Check out my socials below in the footer. Feel free to ask any doubts in comment section or contact me via Contact page I will surely respond. Happy Leetcoding 🙂
Pingback: Leetcode 1614: Maximum Nesting Depth of the Parentheses - Cse Nerd