Valid Parentheses – Leetcode 20 Solution | Code & Explanation

Valid Parentheses – Leetcode 20 Solution in Java

Leetcode’s “Valid Parentheses” problem is one of the classic questions in coding interviews, as it tests your knowledge of stacks and string manipulation. Let’s explore this problem, its requirements, and multiple solutions to solve it efficiently.

Problem Statement

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

An input string is valid if:

• Every close bracket has a corresponding open bracket of the same type.
• Open brackets must be closed by the same type of brackets.
• Open brackets must be closed in the correct order.

Example 1:

  Input: s = "()"
  
  Output: true

Example 2:

  Input: s = "()[]{}"
  
  Output: true

Example 3:

  Input: s = "(]"
  
  Output: false

Example 4:

  Input: s = "([])"
  
  Output: true

Constraints:

1 <= s.length <= 104
s consists of parentheses only '()[]{}'.

Approach

To solve this, we can use a stack data structure, which is ideal for handling last-in, first-out (LIFO) operations, matching the requirement of correctly nested parentheses.

Solution 1: Using a Stack

1. Initialize an empty stack.
2. Iterate over each character in the string:
   • If it’s an opening bracket, push its corresponding closing bracket onto the stack.
   • If it’s a closing bracket, check:
     • If the stack is empty (no matching opening bracket), return false.
     • If the top element of the stack is not the matching bracket, return false.
3. Final Check: If the stack is empty at the end, the string is valid; otherwise, it’s invalid.

Here’s the Java code implementing this solution:

import java.util.Stack;

public class ValidParentheses {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(')');
            } else if (c == '{') {
                stack.push('}');
            } else if (c == '[') {
                stack.push(']');
            } else if (stack.isEmpty() || stack.pop() != c) {
                return false;
            }
        }
        
        return stack.isEmpty();
    }
}

Solution 2: Optimized Stack Implementation

An alternative approach leverages Java’s Deque for efficient stack operations. This implementation is similar but uses Deque’s push and pop methods for better performance.

import java.util.Deque;
import java.util.ArrayDeque;

public class ValidParenthesesOptimized {
    public boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(')');
            } else if (c == '{') {
                stack.push('}');
            } else if (c == '[') {
                stack.push(']');
            } else if (stack.isEmpty() || stack.pop() != c) {
                return false;
            }
        }
        
        return stack.isEmpty();
    }
}

Explanation of Code

• Time Complexity: O(n)O(n)O(n), where nnn is the length of the string, as we traverse each character once.
• Space Complexity: O(n)O(n)O(n) in the worst case, if all characters are opening brackets.

Edge Cases to Consider

1. Single or odd-length strings like "(", "[{", which are invalid.
2. Strings with only closing brackets first like ")]".
3. Balanced strings with nested brackets like "{[()]}".

Conclusion

This problem tests understanding of stacks and helps develop skills in validating nested data structures. The stack-based approach is efficient and easy to implement, making it suitable for handling balanced parentheses scenarios.

Happy coding!