Tagged

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. 
3
4Expression 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.
7
8Problem Constraints:
9   1. 1 <= str.length <= 10⁴
10   2. str consists of parentheses only '()[]{}'. 
11
12Input:  A string
13
14Output: 
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: true
4  Explanation : str contains valid parenthesis

1Example 2 :
2  Input : str = "{}"
3  Output: true 
4  Explanation : str contains valid parenthesis

1Example 3 :
2  Input : str = "({" 
3  Output: false
4  Explanation : open brackets not closed

1Example 4 :
2  Input : str = "([)]"
3  Output: false
4  Explanation : Incorrect closing bracket for an opening bracket. 
5                Here [ is closed by ) which is wrong.

Solution Approaches

Using Stack

Prerequisite

Stack Data Structure

Algorithm

1Input : A String str 
2 
3Step 0: Initialize a stack to store characters 
4Step 1: For each character 'ch' in the given string 'str'  
5Step 2: if ch is an open bracket, then push char into the stack 
6Step 3: else if stack is empty return false 
7Step 4: else if ch is valid closed bracket for the top element of the stack, pop element from the stack 
8Step 5: else, return false 
9Step 6: If stack is not empty, return false 
10        As we have processed all characters of the stack and 
11        still stack is having open brackets 
12Step 7: return true 
13
14Output : true/false

Example Dry Run

Example 1 : ()[]{} - Valid

Example 2 : ()] - Invalid

Example 3: ([)] - Invalid

Example 4: ([ - Invalid

Code Implementation

Java
Python

1import java.util.Stack;
2
3public class ValidParentheses {
4
5    // method to check given expression is valid or not
6    public boolean isValidExpression(String str) {
7        Stack<Character> stack = new Stack<>();
8
9        // traverse through each character of the string
10        for(int i=0; i < str.length(); i++){
11            Character ch = str.charAt(i);
12
13            // if the current character is open bracket push into the stack
14            if(isOpenBracket(ch)) {
15                stack.push(ch);
16            }else {
17
18                // Example 2 : when an expression has a closed bracket,
19                // but no open bracket encountered before closed bracket
20                if(stack.isEmpty()) {
21                    return false;
22                }
23
24                // Example 3 : when an open bracket which is not 
25                // closed with closing bracket
26                if(!isValidPair(stack.peek(), ch)) {
27                    return false;
28                }
29
30                // 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        }
39
40        // Example 1 which is valid
41        return true;
42    }
43
44    // method to check does two brackets valid pair with each other
45    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    }
57
58    // method to check a character is open bracket or not
59    private boolean isOpenBracket(char ch){
60        switch(ch){
61            case '{' :
62            case '(' :
63            case '[' :
64                return true;
65        }
66        return false;
67    }
68
69    // Driver method
70    public static void main(String[] args){
71        ValidParentheses obj = new ValidParentheses();
72
73        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        }
79
80        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        }
86
87        // Case 1 : when an expression has a closed bracket,
88        // but no open bracket encountered before closed bracket
89        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        }
95
96        // Case 2 : when an open bracket is not closing with closing bracket
97        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        }
103
104        // Case 3 : when an expression has only open brackets
105        //          or ended with extra open brackets
106        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

DSA Problems

Stack

Installation

Middle of the Linked List

...