algoadvance

Leetcode 20. Valid Parentheses

Problem Statement:

Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid. An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Clarifying Questions:

1. Is the string only limited to the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’? Yes, the problem specifies that the string will contain only these characters.

2. Is an empty string considered valid? Yes, an empty string should be considered valid since there are no unmatched parentheses.

Strategy:

1. Use a stack to keep track of the opening brackets.
2. Iterate through the string character by character.
   • If the character is an opening bracket (‘(‘ or ‘{‘ or ‘[’), push it onto the stack.
   • If the character is a closing bracket (‘)’ or ‘}’ or ‘]’):
     • Check if the stack is empty. If it is empty, it means there is no corresponding opening bracket for this closing bracket, so return false.
     • Otherwise, pop the top element from the stack and check if it matches the corresponding opening bracket. If not, return false.
3. After processing all characters, check if the stack is empty. If it is not empty, it means there are unmatched opening brackets remaining, so return false.
4. If the stack is empty, return true.

Code:

import java.util.Stack;

public class ValidParentheses {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else if (c == ')' || c == '}' || c == ']') {
                if (stack.isEmpty()) {
                    return false;
                }
                char top = stack.pop();
                if ((c == ')' && top != '(') ||
                    (c == '}' && top != '{') ||
                    (c == ']' && top != '[')) {
                    return false;
                }
            }
        }
        
        return stack.isEmpty();
    }
    
    public static void main(String[] args) {
        ValidParentheses validator = new ValidParentheses();
        System.out.println(validator.isValid("()"));       // true
        System.out.println(validator.isValid("()[]{}"));   // true
        System.out.println(validator.isValid("(]"));       // false
        System.out.println(validator.isValid("([)]"));     // false
        System.out.println(validator.isValid("{[]}"));     // true
    }
}

Time Complexity:

• The time complexity is O(n), where n is the length of the string s. This is because we iterate through each character in the string once.
• The space complexity is also O(n) in the worst case, where all characters are opening brackets and they are all pushed onto the stack.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?