LeetCode 20. Valid Parentheses

Description

https://leetcode.com/problems/valid-parentheses/

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.

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Example 4:

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

Example 5:

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

Constraints:

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

Explanation

The problem is about validating parenthesis in the input string. The input string contains only '(', ')', '{', '}', '[' and ']'.

We could easily solve the problem with a stack.

Start from the first position to visit every character in the string:

• If the character is one left parenthesis, we push it to the stack
• If the character is one right parenthesis, we check if the character matches with the left parenthesis at the top of the stack. If not matched or the stack is empty, the input string fails the test.

Java Solution

public class Solution { 
    public boolean isValid(String s) { 
        Stack<Character> stack = new Stack<Character>(); 
        boolean isValid = false; 
         
        for (int i = 0; i < s.length(); i++) { 
            char ch = s.charAt(i); 
            if (ch == '(' || ch == '{' || ch == '[') { 
                stack.push(ch); 
            } else { 
                if (!stack.isEmpty() && isPair(stack.peek(), ch)) { 
                    stack.pop(); 
                } else { 
                    return false; 
                } 
            } 
        } 
         
        return stack.isEmpty(); 
    } 
 
    private boolean isPairParenthesis(char c1, char c2) { 
        return (c1 == '(' && c2 == ')')  
            || (c1 == '{' && c2 == '}') 
            || (c1 == '[' && c2 == ']'); 
    }     
}


Python Solution

class Solution:
    def isValid(self, s: str) -> bool:
        
        def is_matched_parenthesis(left, right):
            
            return left == '(' and right == ')' or left == '{' and right == '}' or left == '[' and right == ']'
        
        stack = []
        
        for ch in s:
            if ch == '(' or ch == '[' or ch == '{':
                stack.append(ch)
            else:
                if not stack or not is_matched_parenthesis(stack[-1], ch):                
                    return False                    
                else:                
                    stack.pop()
        
        return not stack

• Time complexity: O(N).
• Space complexity: O(N).