0020. Valid Parentheses

Easy | String + Stack | 24 ms (95.97%), 14.3 MB (64.31%)

❓ Problem Statement

Source: LeetCode - Valid Parentheses GitHub: Solution / Performance

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.

✍🏻 Constraints & Example

Constraints:

• 1 <= s.length <= 10^4

• s consists of parentheses only '()[]{}'.

Input: s = "()"
Output: true

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

Input: s = "(]"
Output: false

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

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

💡 Ideas

Use the hash table to record the mapping of parentheses and the stack to store left-side parenthesis for further verification when meeting right-side parenthesis.

• return False if first char is a right-side parenthesis

• return False if the stack is already empty but there is an incoming parenthesis

• return False if the incoming parenthesis doesn't match with the popped item

Note that we need to check whether the stack is empty before returnning the answer. If the stack is not empty but there are no incoming parentheses, return False.

🤖 Python3

class Solution:
    def isValid(self, s: str) -> bool:
        # (base case)fy
        if len(s) == 1: return False
        
        # ==================================================
        #  String + Stack                                  =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        table = { 
            ')': '(', 
            ']': '[', 
            '}': '{' 
        }
        stack = []
        
        # return False if first char is right-side parenthesis
        if s[0] in table: return False
        
        for char in s:
            if char in table:
                # return False if stack is already empty
                if not stack: return False 
                
                if stack.pop() != table[char]: return False
                
            else:
                stack.append( char )
                
        # check stack's capacity before returning True
        return not stack

🤖 Java

class Solution {
    /**
     * @time  : O(n)
     * @space : O(n)
     */
     
    public boolean isValid(String s) {
        /* base case */
        if(s.length() == 1) return false;
        
        HashMap<Character, Character> table = new HashMap<Character, Character>();
        table.put( ')', '(' );
        table.put( '}', '{' );
        table.put( ']', '[' );
        
        if( table.containsKey( s.charAt(0) ) ) return false;
        
        Stack<Character> stack = new Stack<Character>();
        
        for(int i=0 ; i<s.length() ; i++) {
            char c = s.charAt(i);
            
            if(table.containsKey(c)){
                if(stack.isEmpty()) return false;
                
                char top = stack.pop();
                
                if(top != table.get(c)) return false;
                
            } else{
                stack.push(c);
            }
        }
        
        return stack.isEmpty();
    }
}