Easy Stack Problem - Valid Parentheses

I always wanted to explain people how my thought process works when it comes to solving a problem. People around me interested to hear how I tackle a particular question, especially when it involves math or programming logic. So i decided to blog on DSA questions that i solve. In this post i will be discussing the solution of an easy question in leetcode , which is a question based on stack.

Here’s the question

Below is a test case for false

Example 3 : 
Input s = "( { } ]"
Output: false

when considering the order of parentheses in above test case there are 2 opening parentheses followed by 2 ending parentheses ,(p.s. - positioning started from index 1) so there in the 3rd position “ } “ is the closing of “ { “ in the 2nd position and that’s ok for what we are expecting to be true . but in the 4th position there is “ ] “ which is supposed to be the closing bracket of “ ( “ in the first position so that’s a mismatch and condition false .

The strategy is pretty simple , we’ll loop through each character in the string and if it is one of the starting parentheses we have give ( or { or [ we will store its corresponding closing bracket ) or } or ] in the stack and when we are done with opening bracket we’ll compare the remaining closing bracket that they will match the sequence of expected closing bracket stored in the stack.But why stack ? As you know stack uses Last In First Out (LIFO) method , in the stack there will be the closing bracket of most recent opening bracket we encountered while looping through the string , so it will be easy to match that the closing bracket are in correct order corresponding to opening bracket.

Solution :-

import java.util.Stack;

public class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        int i = 0;

        while (i < s.length()) {
            char c = s.charAt(i); 

            if (c == '(') {
                stack.push(')');
            } else if (c == '{') {
                stack.push('}');
            } else if (c == '[') {
                stack.push(']');
            } else {
                if (stack.isEmpty() || stack.pop() != c) {
                    return false;
                }
            }

            i++;
        }

        return stack.isEmpty();
    }
}

Now we can test with an example test case manually to make sure this solution works

Input - "({[]})"

There are 6 characters in the given string , so the loop will iterate for 6 times.

Iteration 1 - '('

• opening bracket so push its matching closing bracket ')'

• Stack [')']

teration 2: '{'

• opening bracket push '}'

• Stack [')', '}']

Iteration 3: '['

• opening bracket push ']'

• Stack [')', '}', ']'

Iteration 4: ']'

• closing bracket pop from stack and check if it matches

• Stack top = ']' Matches so Continue

• Stack [')', '}']

Iteration 5: '}'

• closing bracket pop from stack and check if it matches

• Stack top = '}' Matches , Continue iteration

• Stack [')']

Iteration 6: ')'

• closing bracket pop from stack and check if it matches

• Stack top = ')' Matches Continue

• Stack becomes: []

Now that all iterations are done and the loop completed, also the stack is empty. Since stack.isEmpty() returns true, it means the given string of parentheses is in a valid order.