Java: Valid Parentheses

Thought Process

The problem involves checking if a string of parentheses is valid or not. A string is valid if all types of parentheses i.e. () , [] , {} are properly closed in the correct order. We use a stack to keep track of opening parentheses. For every closing parenthesis, we check if it matches the most recent opening parenthesis on the stack. If we find a closing parenthesis but the stack is empty or the parentheses don't match, the string is invalid. At the end, if the stack is empty, the string is valid; otherwise, it is invalid. 

class Solution {
    public boolean isValid(String s) {
        
        Stack<Character> st = new Stack();

        for(int i=0;i<s.length();i++){

            char ch1 = s.charAt(i);
            if(ch1=='(' || ch1=='[' || ch1=='{'){
                st.push(ch1);
            }
            else{
                if(st.isEmpty()) // To cover this case:  }()
                    return false;
                char ch2 = st.pop(); // It must be an open bracket
                if((ch2=='(' && ch1==')') || (ch2=='[' && ch1==']') || (ch2=='{' && ch1=='}'))
                    continue;
                else
                    return false;
            }
        }
        if(st.isEmpty())
            return true;
        else
            return false;
    }
}

Code Complexity

Time Complexity: O(n)

The algorithm iterates through the string once, where 'n' is the length of the string.

Space Complexity: O(n)

In the worst case, the stack can store up to 'n' elements.

Code copied!