![Amazon Prime](https://technologystrive.com/images/amazonPrime.jpg)
Valid Parentheses Problem
Problem Statement
1Problem Description :2Given a string expression, where it only contains open and closed characters like '(' , ')', '{', '}', '[', ']'. Determine whether "expression" has a valid sequence of closing and opening parenthesis.34Expression will be valid if :5 1.Open brackets must be closed with the same type of brackets.6 2.Open brackets must be closed in the correct order.78Problem Constraints:9 1. 1 <= str.length <= 10⁴10 2. str consists of parentheses only '()[]{}'.1112Input: A string1314Output:15 Return false, if the given expression is not balanced.16 Return true, if the given expression is balanced.
1Example 1 :2 Input : str = "()[]{}"3 Output: true4 Explanation : str contains valid parenthesis
1Example 2 :2 Input : str = "{}"3 Output: true4 Explanation : str contains valid parenthesis
1Example 3 :2 Input : str = "({"3 Output: false4 Explanation : open brackets not closed
1Example 4 :2 Input : str = "([)]"3 Output: false4 Explanation : Incorrect closing bracket for an opening bracket.5 Here [ is closed by ) which is wrong.
Solution Approaches
Using Stack
Prerequisite
Algorithm
1Input : A String str23Step 0: Initialize a stack to store characters4Step 1: For each character 'ch' in the given string 'str'5Step 2: if ch is an open bracket, then push char into the stack6Step 3: else if stack is empty return false7Step 4: else if ch is valid closed bracket for the top element of the stack, pop element from the stack8Step 5: else, return false9Step 6: If stack is not empty, return false10 As we have processed all characters of the stack and11 still stack is having open brackets12Step 7: return true1314Output : true/false
Example Dry Run
Code Implementation
- Java
- Python
1import java.util.Stack;23public class ValidParentheses {45 // method to check given expression is valid or not6 public boolean isValidExpression(String str) {7 Stack<Character> stack = new Stack<>();89 // traverse through each character of the string10 for(int i=0; i < str.length(); i++){11 Character ch = str.charAt(i);1213 // if the current character is open bracket push into the stack14 if(isOpenBracket(ch)) {15 stack.push(ch);16 }else {1718 // Example 2 : when an expression has a closed bracket,19 // but no open bracket encountered before closed bracket20 if(stack.isEmpty()) {21 return false;22 }2324 // Example 3 : when an open bracket which is not25 // closed with closing bracket26 if(!isValidPair(stack.peek(), ch)) {27 return false;28 }2930 // as we found correct pair for the peek element, pop it..31 stack.pop();32 }33 }34 // Example 4: when an expression has only open brackets example {(35 // or ended with extra open brackets (){36 if(!stack.isEmpty()) {37 return false;38 }3940 // Example 1 which is valid41 return true;42 }4344 // method to check does two brackets valid pair with each other45 private boolean isValidPair(char openBracket, char closedBracket){46 if(openBracket == '{' && closedBracket == '}') {47 return true;48 }49 if(openBracket == '[' && closedBracket == ']') {50 return true;51 }52 if(openBracket == '(' && closedBracket == ')') {53 return true;54 }55 return false;56 }5758 // method to check a character is open bracket or not59 private boolean isOpenBracket(char ch){60 switch(ch){61 case '{' :62 case '(' :63 case '[' :64 return true;65 }66 return false;67 }6869 // Driver method70 public static void main(String[] args){71 ValidParentheses obj = new ValidParentheses();7273 String str = "()[]{}";74 if(obj.isValidExpression(str)) {75 System.out.println(str +" is a valid expression") ;76 }else {77 System.out.println(str +" is an invalid expression") ;78 }7980 str = "()";81 if(obj.isValidExpression(str)) {82 System.out.println(str +" is a valid expression") ;83 }else {84 System.out.println(str +" is an invalid expression") ;85 }8687 // Case 1 : when an expression has a closed bracket,88 // but no open bracket encountered before closed bracket89 str = "()]";90 if(obj.isValidExpression(str)) {91 System.out.println(str +" is a valid expression") ;92 }else {93 System.out.println(str +" is an invalid expression") ;94 }9596 // Case 2 : when an open bracket is not closing with closing bracket97 str = "([)]";98 if(obj.isValidExpression(str)) {99 System.out.println(str +" is a valid expression") ;100 }else {101 System.out.println(str +" is an invalid expression") ;102 }103104 // Case 3 : when an expression has only open brackets105 // or ended with extra open brackets106 str = "([{";107 if(obj.isValidExpression(str)) {108 System.out.println(str +" is a valid expression") ;109 }else {110 System.out.println(str +" is an invalid expression") ;111 }112 }113}
Complexity Analysis
- Time Complexity : O(n) where n is the length of the given input string
- Space Complexity: O(n) as we are using stack data structure